Document Open Access Logo

Beyond Natural Proofs: Hardness Magnification and Locality

Authors Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.70.pdf
  • Filesize: 0.86 MB
  • 48 pages

Document Identifiers

Author Details

Lijie Chen
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Shuichi Hirahara
  • National Institute of Informatics, Tokyo, Japan
Igor C. Oliveira
  • University of Warwick, United Kingdom
Ján Pich
  • University of Oxford, United Kingdom
Ninad Rajgopal
  • University of Oxford, United Kingdom
Rahul Santhanam
  • University of Oxford, United Kingdom

Acknowledgements

Part of this work was completed while some of the authors were visiting the Simons Institute for the Theory of Computing. We are grateful to the Simons Institute for their support. This work was supported in part by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2014)/ERC Grant Agreement no. 615075. Ján Pich was supported in part by Grant 19-05497S of GA ČR. Lijie Chen is supported by NSF CCF-1741615 and a Google Faculty Research Award. Igor C. Oliveira was supported in part by a Royal Society University Research Fellowship. (Most of this work was completed while Igor C. Oliveira was affiliated with the University of Oxford.)

Cite AsGet BibTex

Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, and Rahul Santhanam. Beyond Natural Proofs: Hardness Magnification and Locality. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 70:1-70:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.70

Abstract

Hardness magnification reduces major complexity separations (such as EXP ⊈ NC^1) to proving lower bounds for some natural problem Q against weak circuit models. Several recent works [Igor Carboni Oliveira and Rahul Santhanam, 2018; Dylan M. McKay et al., 2019; Lijie Chen and Roei Tell, 2019; Igor Carboni Oliveira et al., 2019; Lijie Chen et al., 2019; Igor Carboni Oliveira, 2019; Lijie Chen et al., 2019] have established results of this form. In the most intriguing cases, the required lower bound is known for problems that appear to be significantly easier than Q, while Q itself is susceptible to lower bounds but these are not yet sufficient for magnification. In this work, we provide more examples of this phenomenon, and investigate the prospects of proving new lower bounds using this approach. In particular, we consider the following essential questions associated with the hardness magnification program: - Does hardness magnification avoid the natural proofs barrier of Razborov and Rudich [Alexander A. Razborov and Steven Rudich, 1997]? - Can we adapt known lower bound techniques to establish the desired lower bound for Q? We establish that some instantiations of hardness magnification overcome the natural proofs barrier in the following sense: slightly superlinear-size circuit lower bounds for certain versions of the minimum circuit size problem MCSP imply the non-existence of natural proofs. As a corollary of our result, we show that certain magnification theorems not only imply strong worst-case circuit lower bounds but also rule out the existence of efficient learning algorithms. Hardness magnification might sidestep natural proofs, but we identify a source of difficulty when trying to adapt existing lower bound techniques to prove strong lower bounds via magnification. This is captured by a locality barrier: existing magnification theorems unconditionally show that the problems Q considered above admit highly efficient circuits extended with small fan-in oracle gates, while lower bound techniques against weak circuit models quite often easily extend to circuits containing such oracles. This explains why direct adaptations of certain lower bounds are unlikely to yield strong complexity separations via hardness magnification.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Hardness Magnification
  • Natural Proofs
  • Minimum Circuit Size Problem
  • Circuit Lower Bounds

Metrics

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

References

  1. Miklós Ajtai. Σ₁¹-formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1-48, 1983. Google Scholar
  2. Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, and Michael E. Saks. Minimizing Disjunctive Normal Form Formulas and AC⁰ Circuits Given a Truth Table. SIAM J. Comput., 38(1):63-84, 2008. URL: https://doi.org/10.1137/060664537.
  3. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. ACM, 57(3):14:1-14:36, 2010. Google Scholar
  4. Alexander E. Andreev and Stasys Jukna. Very large cliques are easy to detect. Discrete Mathematics, 308(16):3717-3721, 2008. URL: https://doi.org/10.1016/j.disc.2007.07.036.
  5. Benny Applebaum, Boaz Barak, and David Xiao. On Basing Lower-Bounds for Learning on Worst-Case Assumptions. In Symposium on Foundations of Computer Science (FOCS), pages 211-220, 2008. Google Scholar
  6. Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. Google Scholar
  7. Louay M. J. Bazzi. Polylogarithmic Independence Can Fool DNF Formulas. SIAM J. Comput., 38(6):2220-2272, 2009. URL: https://doi.org/10.1137/070691954.
  8. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning Algorithms from Natural Proofs. In Conference on Computational Complexity (CCC), pages 10:1-10:24, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.10.
  9. Arkadev Chattopadhyay and Rahul Santhanam. Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. In Symposium on Foundations of Computer Science (FOCS), pages 619-628, 2012. Google Scholar
  10. Lijie Chen, Ce Jin, and Ryan Williams. Hardness Magnification for all Sparse NP Languages. In Symposium on Foundations of Computer Science (FOCS), 2019. Google Scholar
  11. Lijie Chen, Ce Jin, and Ryan Williams. Sharp Threshold Results for Computational Complexity. In Unpublished manuscript, 2019. Google Scholar
  12. Lijie Chen, Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. In Computational Complexity Conference (CCC), 2019. Google Scholar
  13. Lijie Chen and Roei Tell. Bootstrapping Results for Threshold Circuits "Just Beyond" Known Lower Bounds. In Symposium on Theory of Computing (STOC), 2019. Google Scholar
  14. Xi Chen, Igor Carboni Oliveira, and Rocco A. Servedio. Addition is exponentially harder than counting for shallow monotone circuits. In Symposium on Theory of Computing (STOC), pages 1232-1245, 2017. Google Scholar
  15. Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie. AC⁰ ∘ MOD₂ lower bounds for the Boolean Inner Product. J. Comput. Syst. Sci., 97:45-59, 2018. Google Scholar
  16. Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, and Dimitrios Myrisiotis. Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 39:1-39:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.39.
  17. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  18. Jürgen Forster. A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. Syst. Sci., 65(4):612-625, 2002. URL: https://doi.org/10.1016/S0022-0000(02)00019-3.
  19. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. URL: https://doi.org/10.1007/BF01744431.
  20. Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov. Adventures in Monotone Complexity and TFNP. In Innovations in Theoretical Computer Science Conference (ITCS), pages 38:1-38:19, 2019. Google Scholar
  21. Johan Håstad. The Shrinkage Exponent of de Morgan Formulas is 2. SIAM J. Comput., 27(1):48-64, 1998. URL: https://doi.org/10.1137/S0097539794261556.
  22. Shuichi Hirahara. Non-Black-Box Worst-Case to Average-Case Reductions within NP. In Symposium on Foundations of Computer Science (FOCS), pages 247-258, 2018. Google Scholar
  23. Shuichi Hirahara and Rahul Santhanam. On the Average-Case Complexity of MCSP and Its Variants. In Computational Complexity Conference (CCC), pages 7:1-7:20, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.7.
  24. Russell Impagliazzo, Raghu Meka, and David Zuckerman. Pseudorandomness from Shrinkage. J. ACM, 66(2):11:1-11:16, 2019. URL: https://doi.org/10.1145/3230630.
  25. Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks. Size-Depth Tradeoffs for Threshold Circuits. SIAM J. Comput., 26(3):693-707, 1997. Google Scholar
  26. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  27. Russell Impagliazzo and Avi Wigderson. Randomness vs Time: Derandomization under a Uniform Assumption. J. Comput. Syst. Sci., 63(4):672-688, 2001. URL: https://doi.org/10.1006/jcss.2001.1780.
  28. Emil Jerábek. Approximate counting by hashing in bounded arithmetic. J. Symb. Log., 74(3):829-860, 2009. URL: https://doi.org/10.2178/jsl/1245158087.
  29. Stasys Jukna. Boolean Function Complexity - Advances and Frontiers. Springer, 2012. Google Scholar
  30. Jørn Justesen. Class of constructive asymptotically good algebraic codes. IEEE Trans. Information Theory, 18(5):652-656, 1972. URL: https://doi.org/10.1109/TIT.1972.1054893.
  31. Mauricio Karchmer and Avi Wigderson. Monotone Circuits for Connectivity Require Super-Logarithmic Depth. SIAM J. Discrete Math., 3(2):255-265, 1990. URL: https://doi.org/10.1137/0403021.
  32. Ilan Komargodski and Raz Ran. Average-case lower bounds for formula size. In Symposium on Theory of Computing (STOC), 2013. Google Scholar
  33. Swastik Kopparty. On the complexity of powering in finite fields. In Proceedings of the Symposium on Theory of Computing (STOC), pages 489-498, 2011. URL: https://doi.org/10.1145/1993636.1993702.
  34. Jan Krajíček. Forcing with random variables and proof complexity. Cambridge University Press, 2011. Google Scholar
  35. Richard J. Lipton and Ryan Williams. Amplifying circuit lower bounds against polynomial time, with applications. Computational Complexity, 22(2):311-343, 2013. Google Scholar
  36. Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes. In Symposium on Theory of Computing (STOC), 2019. Google Scholar
  37. Moritz Müller and Ján Pich. Feasibly constructive proofs of succinct weak circuit lower bounds. Electronic Colloquium on Computational Complexity (ECCC), 24:144, 2017. URL: https://eccc.weizmann.ac.il/report/2017/144.
  38. Igor Carboni Oliveira. Randomness and Intractability in Kolmogorov Complexity. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 32:1-32:14, 2019. Google Scholar
  39. Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam. Hardness magnification near state-of-the-art lower bounds. In Computational Complexity Conference (CCC), 2019. Google Scholar
  40. Igor Carboni Oliveira and Rahul Santhanam. Majority is Incompressible by AC⁰[p] Circuits. In Conference on Computational Complexity (CCC), pages 124-157, 2015. Google Scholar
  41. Igor Carboni Oliveira and Rahul Santhanam. Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. In Computational Complexity Conference (CCC), pages 18:1-18:49, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.18.
  42. Igor Carboni Oliveira and Rahul Santhanam. Hardness Magnification for Natural Problems. In Symposium on Foundations of Computer Science (FOCS), pages 65-76, 2018. URL: https://doi.org/10.1109/FOCS.2018.00016.
  43. Alexander A. Razborov. Lower bounds on the monotone complexity of some Boolean functions. Doklady Akademii Nauk SSSR, 281:798-801, 1985. English translation in: Soviet Mathematics Doklady 31:354-357, 1985. Google Scholar
  44. Alexander A. Razborov. Lower bounds on the size of constant-depth networks over a complete basis with logical addition. Mathematicheskie Zametki, 41(4):598-607, 1987. Google Scholar
  45. Alexander A. Razborov. Pseudorandom Generators Hard for k-DNF Resolution and Polynomial Calculus Resolution. Annals of Mathematics, 181(2):415-472, 2015. Google Scholar
  46. Alexander A. Razborov and Steven Rudich. Natural Proofs. J. Comput. Syst. Sci., 55(1):24-35, 1997. URL: https://doi.org/10.1006/jcss.1997.1494.
  47. Ben W. Reichardt. Reflections for quantum query algorithms. In Symposium on Discrete Algorithms (SODA), pages 560-569, 2011. Google Scholar
  48. Michael Sipser and Daniel A. Spielman. Expander codes. IEEE Trans. Information Theory, 42(6):1710-1722, 1996. URL: https://doi.org/10.1109/18.556667.
  49. Roman Smolensky. Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In Symposium on Theory of Computing (STOC), pages 77-82, 1987. Google Scholar
  50. Aravind Srinivasan. On the approximability of clique and related maximization problems. J. Comput. Syst. Sci., 67(3):633-651, 2003. Google Scholar
  51. Avishay Tal. Shrinkage of De Morgan Formulae by Spectral Techniques. In Symposium on Foundations of Computer Science (FOCS), pages 551-560, 2014. URL: https://doi.org/10.1109/FOCS.2014.65.
  52. Avishay Tal. Formula lower bounds via the quantum method. In Symposium on Theory of Computing (STOC), pages 1256-1268, 2017. URL: https://doi.org/10.1145/3055399.3055472.
  53. Avishay Tal. Tight Bounds on the Fourier Spectrum of AC⁰. In Computational Complexity Conference (CCC), pages 15:1-15:31, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.15.
  54. Luca Trevisan and Tongke Xue. A Derandomized Switching Lemma and an Improved Derandomization of AC⁰. In Conference on Computational Complexity (CCC), pages 242-247, 2013. URL: https://doi.org/10.1109/CCC.2013.32.
  55. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. URL: https://doi.org/10.1561/0400000010.
  56. Andrew Chi-Chih Yao. Circuits and Local Computation. In Symposium on Theory of Computing (STOC), pages 186-196, 1989. URL: https://doi.org/10.1145/73007.73025.
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