Computer Science/Discrete Mathematics Seminar II

Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Tao and Ziegler showed some general conditions under which such a model exists. Reingold, Trevisan, Tulsiani and Vadhan give a quantitatively improved characterization obtained using an argument based on the Impagliazzo hard-core set theorem (I95) from computational complexity. Gowers (Gow) independently obtained a similar improvement. Recent work by Trevisan, Tulsiani and Vadhan gives a generalization that implies versions of both the hard-core set theorem and the dense model theorem, and gives several applications. Here, we show that the condition under which such models exist can be generalized with a concept we call pseudo-density. We also show that the existence of models can be reduced directly to the improved hardcore distribution results of Holenstein. Using Holenstein's uniform proof of an optimal density hard-core set theorem, we show that the dense models that one derives have a canonical form, with models being (sampleable from) functions defined in terms of tests from the original class. We also give general conditions under which (descriptions of) such models can be efficiently computed. We give some applications, several of which are versions of known results. 1. An immediate application is the connection between computational pseudo-density and pseudo-min-entropy, for distributions of high pseudo-min-entropy. This connection was first observed by Barak, Shaltiel, and Wigderson (BSW03) and implies the dense model theorems. 2. Following RTTV08 and TTV08, we look at tests that are cuts in graphs to get conditions on when a sparse graph ``looks like'' a dense graph. We reprove and generalize results of Kohayakawa (Koh97) and Alon, Coja-Oghlan, Han, Kang, Rodl, and Schacht (ACHKRS07). 3. As toy examples, we apply the general results to sets of tests consisting of monomials or small juntas. For example, we show that for each $k, C $ there are $l, \delta$ so that for any distribution $D$ over the hypercube, either there is an $l$-junta that has at least a $\delta$ probability of being true under the uniform distribution and is $C$ times as likely under $D$ as it is in the uniform distribution, or there is a distribution $D'$ $\delta$-indistinguishable from $D$ by $k$-juntas, where $D'$ has relative measure at least $\delta$ within the uniform distribution, and $D'(x_1,..x_n)$ only depends on at most $l$ of its coordinates.