License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.2
URN: urn:nbn:de:0030-drops-135417
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13541/
Go to the corresponding LIPIcs Volume Portal

Impagliazzo, Russell ; McGuire, Sam

Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?)

pdf-format:
LIPIcs-ITCS-2021-2.pdf (0.6 MB)

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 so-called dense model theorem of Green and Tao (and later made explicit by Tao-Zeigler, 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:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{James R. Lee},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13541},
  URN =		{urn:nbn:de:0030-drops-135417},
  doi =		{10.4230/LIPIcs.ITCS.2021.2},
  annote =	{Keywords: Computational entropy, dense model theorem, coin problem}
}

Keywords: Computational entropy, dense model theorem, coin problem
Collection: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Issue Date: 2021
Date of publication: 04.02.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI