Impagliazzo, Russell ;
McGuire, Sam
Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?)
Abstract
Computational pseudorandomness studies the extent to which a random variable Z looks like the uniform distribution according to a class of tests ℱ. Computational entropy generalizes computational pseudorandomness by studying the extent which a random variable looks like a high entropy distribution. There are different formal definitions of computational entropy with different advantages for different applications. Because of this, it is of interest to understand when these definitions are equivalent.
We consider three notions of computational entropy which are known to be equivalent when the test class ℱ is closed under taking majorities. This equivalence constitutes (essentially) the socalled dense model theorem of Green and Tao (and later made explicit by TaoZeigler, Reingold et al., and Gowers). The dense model theorem plays a key role in Green and Tao’s proof that the primes contain arbitrarily long arithmetic progressions and has since been connected to a surprisingly wide range of topics in mathematics and computer science, including cryptography, computational complexity, combinatorics and machine learning. We show that, in different situations where ℱ is not closed under majority, this equivalence fails. This in turn provides examples where the dense model theorem is false.
BibTeX  Entry
@InProceedings{impagliazzo_et_al:LIPIcs.ITCS.2021.2,
author = {Russell Impagliazzo and Sam McGuire},
title = {{Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?)}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {2:12:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13541},
URN = {urn:nbn:de:0030drops135417},
doi = {10.4230/LIPIcs.ITCS.2021.2},
annote = {Keywords: Computational entropy, dense model theorem, coin problem}
}
04.02.2021
Keywords: 

Computational entropy, dense model theorem, coin problem 
Seminar: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Issue date: 

2021 
Date of publication: 

04.02.2021 