Abstract
We prove a lower bound on the amount of nonuniform advice needed by blackbox 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 deltadense in a distribution that is epsilon'indistinguishable from uniform, there exists a "dense model" for D, that is, a distribution that is deltadense in the uniform distribution and is epsilonindistinguishable from D. This epsilonindistinguishability 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)} logF) 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) logF). Our lower bound can be viewed as an analog of list size lower bounds for listdecoding of errorcorrecting 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 pbiased 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.
BibTeX  Entry
@InProceedings{watson:LIPIcs:2013:3971,
author = {Thomas Watson},
title = {{Advice Lower Bounds for the Dense Model Theorem}},
booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages = {634645},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897507},
ISSN = {18688969},
year = {2013},
volume = {20},
editor = {Natacha Portier and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/3971},
URN = {urn:nbn:de:0030drops39717},
doi = {10.4230/LIPIcs.STACS.2013.634},
annote = {Keywords: Pseudorandomness, advice lower bounds, dense model theorem}
}
Keywords: 

Pseudorandomness, advice lower bounds, dense model theorem 
Collection: 

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) 
Issue Date: 

2013 
Date of publication: 

26.02.2013 