Dense Subsets of Pseudorandom Sets

A theorem of Green, Tao, and Ziegler can be stated (roughly) as follows: ifR is a pseudorandom set, and D is a dense subset of R, then D may be modeled by a set M that is dense in the entire domain such that D and M are indistinguishable. (The precise statement refers to"measures" or distributions rather than sets.) The proof of this theorem is very general, and it applies to notions of pseudo-randomness and indistinguishability defined in terms of any family of distinguishers with some mild closure properties. The proof proceeds via iterative partitioning and an energy increment argument, in the spirit of the proof of the weak Szemeredi regularity lemma. The "reduction" involved in the proof has exponential complexity in the distinguishing probability. We present a new proof inspired by Nisan's proof of Impagliazzo's hardcore set theorem. The reduction in our proof has polynomial complexity in the distinguishing probability and provides a new characterization of the notion of "pseudoentropy" of a distribution. A proof similar to ours has also been independently discovered by Gowers [2]. We also follow the connection between the two theorems and obtain a new proof of Impagliazzo's hardcore set theorem via iterative partitioning and energy increment. While our reduction has exponential complexity in some parameters, it has the advantage that the hardcore set is efficiently recognizable.

Authors

• Omer Reingold
• Luca Trevisan 0001
• Madhur Tulsiani
• Salil P. Vadhan

Keywords

• Arithmetic
• Polynomials
• Complexity theory
• Cryptography
• Additives
• Combinatorial mathematics
• Computer science
• Research and development
• Dense Set
• Proof Of Theorem
• Energy Increment
• Uniform Distribution
• Computational Efficiency
• Density Distribution
• Density Model
• Theorem States
• Set Of Integers
• Finite Domain
• Random Input
• Sparse Graph
• Boolean Function
• Input Fractions
• pseudorandomness
• additive combinatorics
• regularity lemmas
• pseudoentropy