2026-08-11T21:21:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3971 2024-03-06T10:34:44Z ddc:004 open_access

Advice Lower Bounds for the Dense Model Theorem Watson, Thomas Pseudorandomness advice lower bounds dense model theorem We prove a lower bound on the amount of nonuniform advice needed by black-box reductions for the Dense Model Theorem of Green, Tao, and Ziegler, and of Reingold, Trevisan, Tulsiani, and Vadhan. The latter theorem roughly says that for every distribution D that is delta-dense in a distribution that is epsilon'-indistinguishable from uniform, there exists a "dense model" for D, that is, a distribution that is delta-dense in the uniform distribution and is epsilon-indistinguishable from D. This epsilon-indistinguishability is with respect to an arbitrary small class of functions F. For the natural case where epsilon' >= Omega(epsilon delta) and epsilon >= delta^{O(1)}, our lower bound implies that Omega(sqrt{(1/epsilon)log(1/delta)} log|F|) advice bits are necessary. There is only a polynomial gap between our lower bound and the best upper bound for this case (due to Zhang), which is O((1/epsilon^2)log(1/delta) log|F|). Our lower bound can be viewed as an analog of list size lower bounds for list-decoding of error-correcting codes, but for "dense model decoding" instead. Our proof introduces some new techniques which may be of independent interest, including an analysis of a majority of majorities of p-biased bits. The latter analysis uses an extremely tight lower bound on the tail of the binomial distribution, which we could not find in the literature. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Watson 2013 Is Part Of LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2013.634 urn:nbn:de:0030-drops-39717 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.634 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode