Document Open Access Logo

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

Authors Russell Impagliazzo, Sam McGuire

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.2.pdf
  • Filesize: 0.55 MB
  • 20 pages

Document Identifiers

Author Details

Russell Impagliazzo
  • CSE Department, University of California San Diego, La Jolla, CA, USA
Sam McGuire
  • CSE Department, University of California San Diego, La Jolla, CA, USA

Funding

Research supported by NSF award 1909634 and a Simons Investigator award.

Cite AsGet BibTex

Russell Impagliazzo and Sam McGuire. Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.2

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Computational entropy
  • dense model theorem
  • coin problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Scott Aaronson. Bqp and the polynomial hierarchy. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 141-150, 2010. Google Scholar
  2. Rohit Agrawal. Coin theorems and the fourier expansion. arXiv preprint, 2019. URL: http://arxiv.org/abs/1906.03743.
  3. Miklos Ajtai and Avi Wigderson. Deterministic simulation of probabilistic constant depth circuits. In 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pages 11-19. IEEE, 1985. Google Scholar
  4. Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289-304, 1992. Google Scholar
  5. Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (gans). In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 224-232. JMLR. org, 2017. Google Scholar
  6. R.B. Ash. Information Theory. Dover books on advanced mathematics. Dover Publications, 1990. URL: https://books.google.com/books?id=nJ3UmGvdUCoC.
  7. Boaz Barak, Moritz Hardt, and Satyen Kale. The uniform hardcore lemma via approximate bregman projections. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 1193-1200. SIAM, 2009. Google Scholar
  8. Boaz Barak, Ronen Shaltiel, and Avi Wigderson. Computational analogues of entropy. In Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques, pages 200-215. Springer, 2003. Google Scholar
  9. Thomas F Bloom and Olof Sisask. Breaking the logarithmic barrier in roth’s theorem on arithmetic progressions. arXiv preprint, 2020. URL: http://arxiv.org/abs/2007.03528.
  10. Joshua Brody and Elad Verbin. The coin problem and pseudorandomness for branching programs. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 30-39. IEEE, 2010. Google Scholar
  11. Mei-Chu Chang et al. A polynomial bound in freiman’s theorem. Duke mathematical journal, 113(3):399-419, 2002. Google Scholar
  12. Gil Cohen, Anat Ganor, and Ran Raz. Two sides of the coin problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014. Google Scholar
  13. Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman. Nearly optimal pseudorandomness from hardness. Technical report, ECCC preprint TR19-099, 2019. Google Scholar
  14. Stefan Dziembowski and Krzysztof Pietrzak. Leakage-resilient cryptography. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 293-302. IEEE, 2008. Google Scholar
  15. Yoav Freund and Robert Schapire. A short introduction to boosting. Journal-Japanese Society For Artificial Intelligence, 14(771-780):1612, 1999. Google Scholar
  16. W. T. Gowers. A new proof of szemerédi’s theorem. Geometric & Functional Analysis GAFA, 11(3):465-588, 2001. Google Scholar
  17. W. T. Gowers. Decompositions, approximate structure, transference, and the hahn-banach theorem. Bulletin of the London Mathematical Society, 42(4):573-606, 2010. Google Scholar
  18. Ben Green and Terence Tao. The primes contain arbitrarily long arithmetic progressions. Annals of Mathematics, pages 481-547, 2008. Google Scholar
  19. Aryeh Grinberg, Ronen Shaltiel, and Emanuele Viola. Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 956-966. IEEE, 2018. Google Scholar
  20. Iftach Haitner, Omer Reingold, and Salil Vadhan. Efficiency improvements in constructing pseudorandom generators from one-way functions. SIAM Journal on Computing, 42(3):1405-1430, 2013. Google Scholar
  21. Iftach Haitner, Omer Reingold, Salil Vadhan, and Hoeteck Wee. Inaccessible entropy. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 611-620, 2009. Google Scholar
  22. Lianna Hambardzumyan and Yaqiao Li. Chang’s lemma via pinsker’s inequality. Discrete Mathematics, 343(1):111496, 2020. Google Scholar
  23. Johan Håstad. Computational limitations of small-depth circuits. MIT Press, 1987. Google Scholar
  24. Johan Håstad. On the correlation of parity and small-depth circuits. SIAM Journal on Computing, 43(5):1699-1708, 2014. Google Scholar
  25. Johan Håstad, Russell Impagliazzo, Leonid A Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364-1396, 1999. Google Scholar
  26. Thomas Holenstein. Key agreement from weak bit agreement. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 664-673, 2005. Google Scholar
  27. Chun-Yuan Hsiao, Chi-Jen Lu, and Leonid Reyzin. Conditional computational entropy, or toward separating pseudoentropy from compressibility. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 169-186. Springer, 2007. Google Scholar
  28. Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 538-545. IEEE, 1995. Google Scholar
  29. Russell Impagliazzo. Connections between pseudo-randomness and machine learning: boosting, dense models, and regularity, 2020. Google Scholar
  30. Russell Impagliazzo, William Matthews, and Ramamohan Paturi. A satisfiability algorithm for ac0. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 961-972. SIAM, 2012. Google Scholar
  31. Russell Impagliazzo, Cristopher Moore, and Alexander Russell. An entropic proof of chang’s inequality. SIAM Journal on Discrete Mathematics, 28(1):173-176, 2014. Google Scholar
  32. Adam R Klivans and Rocco A Servedio. Boosting and hard-core set construction. Machine Learning, 51(3):217-238, 2003. Google Scholar
  33. Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S Venkitesh. A fixed-depth size-hierarchy theorem for AC⁰[⊕] via the coin problem. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 442-453, 2019. Google Scholar
  34. Chi-Jen Lu, Shi-Chun Tsai, and Hsin-Lung Wu. Complexity of hard-core set proofs. computational complexity, 20(1):145-171, 2011. Google Scholar
  35. Or Meir and Avi Wigderson. Prediction from partial information and hindsight, with application to circuit lower bounds. computational complexity, 28(2):145-183, 2019. Google Scholar
  36. Ilya Mironov, Omkant Pandey, Omer Reingod, and Salil Vadhan. Computational differential privacy. In Annual International Cryptology Conference, pages 126-142. Springer, 2009. Google Scholar
  37. Alexander A Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333-338, 1987. Google Scholar
  38. Omer Reingold, Luca Trevisan, Madhur Tulsiani, and Salil Vadhan. Dense subsets of pseudorandom sets. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 76-85. IEEE, 2008. Google Scholar
  39. Benjamin Rossman. An entropy proof of the switching lemma and tight bounds on the decision-tree size of ac0, 2017. Google Scholar
  40. Rocco A Servedio and Li-Yang Tan. Improved pseudorandom generators from pseudorandom multi-switching lemmas. arXiv preprint, 2018. URL: http://arxiv.org/abs/1801.03590.
  41. Ronen Shaltiel. Is it possible to improve yao’s xor lemma using reductions that exploit the efficiency of their oracle? In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  42. Ronen Shaltiel and Emanuele Viola. Hardness amplification proofs require majority. SIAM Journal on Computing, 39(7):3122-3154, 2010. Google Scholar
  43. Roman Smolensky. On representations by low-degree polynomials. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 130-138. IEEE, 1993. Google Scholar
  44. Srikanth Srinivasan. A robust version of hegedus’s lemma, with applications. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1349-1362. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384328.
  45. Endre Szemerédi. On sets of integers containing no four elements in arithmetic progression. Acta Mathematica Academiae Scientiarum Hungarica, 20(1-2):89-104, 1969. Google Scholar
  46. Avishay Tal. Tight bounds on the fourier spectrum of ac0. In 32nd Computational Complexity Conference (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  47. Michel Talagrand. How much are increasing sets positively correlated? Combinatorica, 16(2):243-258, 1996. Google Scholar
  48. Terence Tao, Tamar Ziegler, et al. The primes contain arbitrarily long polynomial progressions. Acta Mathematica, 201(2):213-305, 2008. Google Scholar
  49. Luca Trevisan, Madhur Tulsiani, and Salil Vadhan. Regularity, boosting, and efficiently simulating every high-entropy distribution. In 2009 24th Annual IEEE Conference on Computational Complexity, pages 126-136. IEEE, 2009. Google Scholar
  50. Thomas Watson. Advice lower bounds for the dense model theorem. ACM Transactions on Computation Theory (TOCT), 7(1):1-18, 2015. Google Scholar
  51. Andrew C Yao. Theory and application of trapdoor functions. In 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982), pages 80-91. IEEE, 1982. Google Scholar
  52. Jiapeng Zhang. On the query complexity for showing dense model. Electron. Colloquium Comput. Complex., 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact