Members’ Seminar
Recursively Applying Constructive Dense Model Theorems and Weak Regularity
Green and Tao [GT] used the existence of a dense subset indistinguishable from theprimes under certain tests from a certain class to prove the existence of arbitrarily longprime arithmetic progressions. Tao and Ziegler [TZ] showedsome general conditions un-der which such a model exists. Independently, Barak, Shaltiel and Wigderson [BSW] hadalso given such a characterization from a complexity-theoretic standpoint. In [RTTV], aquantitatively improved characterization was obtained using an argument based on Nisan’sproof of the Impagliazzo hard-core set theorem [I95] from computational complexity. Gow-ers [Gow] independently obtained a similar improvement. Trevisan, Tulsiani and Vadhan [TTV] give a decomposition theorem that generalizes both the dense model theorem and the hard-core set theorem, and show connections between dense model theorems and the weakgraph regularity results of Frieze and Kannan.
In this talk, we look at constructive and recursive versions of dense model theorems. A constructive version is one in which the model itself is definable in terms of the same class of distinguishing tests for which it is indistinguishable from the set. We show a decomposition theorem based on an iterative use of dense model theorems, and then show that it is equivalent to that of [TTV]. However, in addition, we can use this decomposition theorem recursively to get stronger decomposition theorems.
We give several applications, including generalizations of weak regularity lemmas [FK, Koh, COCF]. For example, we show that any graph $G$ with $\Delta n^2$ edges has a $\gamma$-cut-approximator of rank $2^{poly(1/\gamma,1/\log(1/\Delta)}$, whereas direct application of [FK] gives rank $2^{O(1/\gamma^2\Delta^2)}$.
References:
[GT] Ben Green and Terence Tao, The primes contain arbitrarily long arithmetic progressions. To appear: Annals of mathematics, manuscript: 2004.
[TZ] Terence Tao and Tamar Ziegler. The primes contain arbitrarily long polynomial progressions. arXiv:math/060050, 2006.
[BSW] Boaz Barak, Ronen Shaltiel, Avi Wigderson: Computational Analogues of Entropy. RANDOM-APPROX 2003, pp. 200-215.
[RTTV] Omer Reingold, Luca Trevisan, Madhur Tulsiani and Salil Vadhan: Dense Subsets of Pseudorandom Sets, FOCS 2008, pp. 76-85.
[I95] R. Impagliazzo, Hard-Core Distributions for Somewhat Hard Problems. FOCS 1995, pp. 538-545.
[Gow] Timothy Gowers. Decompositions, approximate structure, transference, and the Hahn-Banach theorem. Preprint, 2008.
[TTV] Luca Trevisan, Madhur Tulsiani and Salil Vadhan: Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution, IEEE Computational Complexity Conference, 2009, pp.126-136.
[FK] A. Frieze and R. Kannan, Quick approximations to matrices and applications. Combinatorica, volume 19, 1999, pp. 175-220.
[Koh] Y. Kohayakawa: Szemeredi’s regularity lemma for sparse graphs. In F. Cucker, M. Shub (editors): Foundations of computational mathematics, 1997, pp. 216-230.
[COCF] Amin Coja-Oghlan, Colin Cooper, Alan Frieze: An efficient regularity concept for sparse graphs and matrices. Proc. 20th SODA, 207-216.