Document Open Access Logo

Black-Box Constructive Proofs Are Unavoidable

Authors Lijie Chen , Ryan Williams , Tianqi Yang

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2023.35.pdf
  • Filesize: 0.99 MB
  • 24 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • Circuit lower bounds
  • natural proofs
  • probabilistic checkable proofs

Metrics

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

Abstract

Following Razborov and Rudich, a "natural property" for proving a circuit lower bound satisfies three axioms: constructivity, largeness, and usefulness. In 2013, Williams proved that for any reasonable circuit class C, NEXP ⊂ C is equivalent to the existence of a constructive property useful against C. Here, a property is constructive if it can be decided in poly(N) time, where N = 2ⁿ is the length of the truth-table of the given n-input function.
Recently, Fan, Li, and Yang initiated the study of black-box natural properties, which require a much stronger notion of constructivity, called black-box constructivity: the property should be decidable in randomized polylog(N) time, given oracle access to the n-input function. They showed that most proofs based on random restrictions yield black-box natural properties, and demonstrated limitations on what black-box natural properties can prove. 
In this paper, perhaps surprisingly, we prove that the equivalence of Williams holds even with this stronger notion of black-box constructivity: for any reasonable circuit class C, NEXP ⊂ C is equivalent to the existence of a black-box constructive property useful against C. The main technical ingredient in proving this equivalence is a smooth, strong, and locally-decodable probabilistically checkable proof (PCP), which we construct based on a recent work by Paradise. As a by-product, we show that average-case witness lower bounds for PCP verifiers follow from NEXP lower bounds.
We also show that randomness is essential in the definition of black-box constructivity: we unconditionally prove that there is no deterministic polylog(N)-time constructive property that is useful against even polynomial-size AC⁰ circuits.

Cite As Get BibTex

Lijie Chen, Ryan Williams, and Tianqi Yang. Black-Box Constructive Proofs Are Unavoidable. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 35:1-35:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.35

Author Details

Lijie Chen
  • Miller Institute for Basic Research in Science, UC Berkeley, CA, USA
Ryan Williams
  • CSAIL, MIT, Cambridge, MA, USA
Tianqi Yang
  • IIIS, Tsinghua University, Beijing, China

Funding

  • Williams, Ryan: Supported by NSF CCF-2127597.

Acknowledgements

We would also like to thank Jiatu Li for discussions during the early stage of this research project and anonymous reviewers for their comments.

References

  1. Eric Allender. Cracks in the defenses: Scouting out approaches on circuit lower bounds. In Computer Science - Theory and Applications, Third International Computer Science Symposium in Russia, CSR 2008, Moscow, Russia, June 7-12, 2008, Proceedings, volume 5010 of Lecture Notes in Computer Science, pages 3-10. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-79709-8_2.
  2. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. ACM, 57(3):14:1-14:36, 2010. Google Scholar
  3. Josh Alman and Lijie Chen. Efficient construction of rigid matrices using an NP oracle. In Proc. 60th FOCS, pages 1034-1055. IEEE Comp. Soc., 2019. URL: https://doi.org/10.1109/FOCS.2019.00067.
  4. Alexander E Andreev. On a method for obtaining more than quadratic effective lower bounds for the complexity of π-schemes. Moscow Univ. Math. Bull., 42(1):63-66, 1987. Google Scholar
  5. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
  6. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, 1998. URL: https://doi.org/10.1145/278298.278306.
  7. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70-122, 1998. URL: https://doi.org/10.1145/273865.273901.
  8. Eli Ben-Sasson and Emanuele Viola. Short PCPs with projection queries. In Proc. 41st Internat. Colloq. on Automata, Languages and Programming (ICALP'14), pages 163-173. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_14.
  9. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Agnostic learning from tolerant natural proofs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, volume 81 of LIPIcs, pages 35:1-35:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.35.
  10. Brynmor Chapman and Ryan Williams. The circuit-input game, natural proofs, and testing circuits with data. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 263-270. ACM, 2015. URL: https://doi.org/10.1145/2688073.2688115.
  11. Lijie Chen, Shuichi Hirahara, Igor Carboni 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, pages 70:1-70:48, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.70.
  12. Lijie Chen, Ce Jin, and R. Ryan Williams. Sharp threshold results for computational complexity. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1335-1348. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384283.
  13. Timothy Y. Chow. Almost-natural proofs. J. Comput. Syst. Sci., 77(4):728-737, 2011. URL: https://doi.org/10.1016/j.jcss.2010.06.017.
  14. Zhiyuan Fan, Jiatu Li, and Tianqi Yang. The exact complexity of pseudorandom functions and tight barriers to lower bound proofs. Electron. Colloquium Comput. Complex., page 125, 2021. URL: https://eccc.weizmann.ac.il/report/2021/125, URL: http://arxiv.org/abs/TR21-125.
  15. Oded Goldreich and Avi Wigderson. On derandomizing algorithms that err extremely rarely. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 109-118. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591808.
  16. Prahladh Harsha. Robust PCPs of Proximity and Shorter PCPs. PhD thesis, Massachusetts Institute of Technology, 2004. Google Scholar
  17. 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.
  18. Alexander Healy and Emanuele Viola. Constant-depth circuits for arithmetic in finite fields of characteristic two. In STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings, volume 3884 of Lecture Notes in Computer Science, pages 672-683. Springer, 2006. URL: https://doi.org/10.1007/11672142_55.
  19. Matthias Krause and Stefan Lucks. Pseudorandom functions in tc^0 and cryptographic limitations to proving lower bounds. Comput. Complex., 10(4):297-313, 2001. URL: https://doi.org/10.1007/s000370100002.
  20. Richard J. Lipton and Ryan Williams. Amplifying circuit lower bounds against polynomial time, with applications. Comput. Complex., 22(2):311-343, 2013. Google Scholar
  21. Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 1215-1225. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316396.
  22. Eric Miles and Emanuele Viola. Substitution-permutation networks, pseudorandom functions, and natural proofs. J. ACM, 62(6):46:1-46:29, 2015. URL: https://doi.org/10.1145/2792978.
  23. Dana Moshkovitz and Ran Raz. Two-query PCP with subconstant error. J. ACM, 57(5):29:1-29:29, 2010. URL: https://doi.org/10.1145/1754399.1754402.
  24. Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudo-random functions. J. ACM, 51(2):231-262, 2004. URL: https://doi.org/10.1145/972639.972643.
  25. Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam. Hardness magnification near state-of-the-art lower bounds. In 34th Computational Complexity Conference, CCC 2019, pages 27:1-27:29, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.27.
  26. Igor Carboni Oliveira and Rahul Santhanam. Hardness magnification for natural problems. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 65-76, 2018. URL: https://doi.org/10.1109/FOCS.2018.00016.
  27. Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43(3):425-440, 1991. URL: https://doi.org/10.1016/0022-0000(91)90023-X.
  28. Orr Paradise. Smooth and strong pcps. Comput. Complex., 30(1):1, 2021. URL: https://doi.org/10.1007/s00037-020-00199-3.
  29. Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. J. ACM, 26(2):361-381, 1979. URL: https://doi.org/10.1145/322123.322138.
  30. 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.
  31. Avishay Tal. Shrinkage of de morgan formulae by spectral techniques. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 551-560. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/FOCS.2014.65.
  32. Avishay Tal. Formula lower bounds via the quantum method. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1256-1268. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055472.
  33. R. Ryan Williams. Natural proofs versus derandomization. SIAM J. Comput., 45(2):497-529, 2016. URL: https://doi.org/10.1137/130938219.
  34. R. Ryan Williams. New algorithms and lower bounds for circuits with linear threshold gates. Theory Comput., 14(1):1-25, 2018. URL: https://doi.org/10.4086/toc.2018.v014a017.
  35. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. SIAM J. Comput., 42(3):1218-1244, 2013. URL: https://doi.org/10.1137/10080703X.
  36. Ryan Williams. Natural proofs versus derandomization. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 21-30. ACM, 2013. URL: https://doi.org/10.1145/2488608.2488612.
  37. Ryan Williams. Nonuniform ACC circuit lower bounds. J. ACM, 61(1):2, 2014. URL: https://doi.org/10.1145/2559903.
  38. Stanislav Žák. A Turing machine time hierarchy. Theoretical Computer Science, 26(3):327-333, 1983. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact