Document Open Access Logo

Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]

Author Rahul Ilango

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.34.pdf
  • Filesize: 0.66 MB
  • 26 pages

Document Identifiers

Author Details

Rahul Ilango
  • Massachusetts Institute of Technology, Cambridge, MA, USA

Funding

This work was supported (in part) by an Akamai Presidential Fellowship.

Acknowledgements

I would like to give a special thanks to Eric Allender for innumerable suggestions and perspectives during all stages of this work. To name just a single example, one of his suggestions led me to improve a PARITY-reduction to the presented MAJORITY-reduction for (AC^0_d)-MCSP. I would also like to thank Abhishek Bhrushundi and Aditi Dudeja for their help in results about constant depth formulas that lead to this paper. I am grateful to Ryan Williams for asking interesting questions and helping to improve the exposition of the paper. Finally, I thank Harry Buhrman, Lance Fortnow, Igor Oliveira, Ján Pich, Aditya Potukuchi, Ninad Rajgopal, Michael Saks, and Rahul Santhanam for answering my questions and engaging in many useful discussions about this work.

Cite As Get BibTex

Rahul Ilango. Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 34:1-34:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITCS.2020.34

Abstract

The Minimum Circuit Size Problem (MCSP) asks whether a given Boolean function has a circuit of at most a given size. MCSP has been studied for over a half-century and has deep connections throughout theoretical computer science including to cryptography, computational learning theory, and proof complexity. For example, we know (informally) that if MCSP is easy to compute, then most cryptography can be broken. Despite this cryptographic hardness connection and extensive research, we still know relatively little about the hardness of MCSP unconditionally. Indeed, until very recently it was unknown whether MCSP can be computed in AC^0[2] (Golovnev et al., ICALP 2019). 
Our main contribution in this paper is to formulate a new "oracle" variant of circuit complexity and prove that this problem is NP-complete under randomized reductions. In more detail, we define the Minimum Oracle Circuit Size Problem (MOCSP) that takes as input the truth table of a Boolean function f, a size threshold s, and the truth table of an oracle Boolean function O, and determines whether there is a circuit with O-oracle gates and at most s wires that computes f. We prove that MOCSP is NP-complete under randomized polynomial-time reductions. 
We also extend the recent AC^0[p] lower bound against MCSP by Golovnev et al. to a lower bound against the circuit minimization problem for depth-d formulas, (AC^0_d)-MCSP. We view this result as primarily a technical contribution. In particular, our proof takes a radically different approach from prior MCSP-related hardness results.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Minimum Circuit Size Problem
  • reductions
  • NP-completeness
  • circuit lower bounds

Metrics

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

Related Versions

References

  1. E. Allender, L. Hellerstein, P. McCabe, T. Pitassi, and M. Saks. Minimizing DNF formulas and AC0d circuits given a truth table. In 21st Annual IEEE Conference on Computational Complexity (CCC'06), pages 15 pp.-251, July 2006. Google Scholar
  2. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from Random Strings. SIAM J. Comput., 35(6):1467-1493, 2006. Google Scholar
  3. Eric Allender and Bireswar Das. Zero Knowledge and Circuit Minimization. Information and Computation, 256:2-8, 2017. Google Scholar
  4. Eric Allender and Shuichi Hirahara. New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems. In Symposium on Mathematical Foundations of Computer Science (MFCS), pages 54:1-54:14, 2017. Google Scholar
  5. Eric Allender, Dhiraj Holden, and Valentine Kabanets. The Minimum Oracle Circuit Size Problem. Computational Complexity, 26(2):469-496, 2017. Google Scholar
  6. Eric Allender, Michal Koucký, Detlef Ronneburger, and Sambuddha Roy. The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. Journal of Computer and System Sciences, 77(1):14-40, 2011. Google Scholar
  7. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Google Scholar
  8. Harry Buhrman and Leen Torenvliet. Randomness is Hard. SIAM Journal on Computing, 30:200-1, 2000. Google Scholar
  9. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning Algorithms from Natural Proofs. In Computational Complexity Conference (CCC), pages 10:1-10:24, 2016. Google Scholar
  10. Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, and Dimitrios Myrisiotis. Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. In 46th International Colloquium on Automata, Languages, and Programming, ICALP, pages 39:1-39:14, 2019. Google Scholar
  11. Irit Dinur and David Steurer. Analytical Approach to Parallel Repetition. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 624-633, 2014. Google Scholar
  12. Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal. AC0[p] lower bounds against MCSP via the coin problem. Electronic Colloquium on Computational Complexity, TR19-018, 2019. Google Scholar
  13. G.H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers. Clarendon Press, Oxford, England, 5th edition, 1979. Google Scholar
  14. 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
  15. Shuichi Hirahara, Igor C. Oliveira, and Rahul Santhanam. NP-hardness of minimum circuit size problem for OR-AND-MOD circuits. In Computational Complexity Conference (CCC), pages 5:1-5:31, 2018. Google Scholar
  16. Shuichi Hirahara and Osamu Watanabe. Limits of minimum circuit size problem as oracle. In Computational Complexity Conference (CCC), pages 18:1-18:20, 2016. Google Scholar
  17. John Hitchcock and Aduri Pavan. On the NP-Completeness of the Minimum Circuit Size Problem. In Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS), 2015. Google Scholar
  18. Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich. The Power of Natural Properties As Oracles. In Proceedings of the 33rd Computational Complexity Conference, CCC '18, pages 7:1-7:20, 2018. Google Scholar
  19. Valentine Kabanets and Jin-Yi Cai. Circuit Minimization Problem. In Proceedings of ACM Symposium on Theory of Computing (STOC), pages 73-79, 2000. Google Scholar
  20. William J. Masek. Some NP-complete Set Covering Problems. Unpublished Manuscript, 1979. Google Scholar
  21. Colin McDiarmid. On the method of bounded differences. In Surveys in Combinatorics, (Norwich, 1989), London Math. Soc. Lecture Note Ser. 141 . Cambridge Univ. Press, Cambridge, (1989), pp. 48–188. Google Scholar
  22. 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, Phoenix, AZ, USA, June 23-26, 2019., pages 1215-1225, 2019. Google Scholar
  23. Cody D. Murray and R. Ryan Williams. On the (Non) NP-hardness of Computing Circuit Complexity. In Computational Complexity Conference (CCC), pages 365-380, 2015. Google Scholar
  24. Noam Nisan and Avi Wigderson. Hardness vs Randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. Google Scholar
  25. Igor C. Oliveira, Ján Pich, and Rahul Santhanam. Hardness magnification near state-of-the-art lower bounds. Electronic Colloquium on Computational Complexity, TR18-158, 2018. Google Scholar
  26. Igor C. Oliveira and Rahul Santhanam. Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. In Computational Complexity Conference (CCC), pages 18:1-18:49, 2017. Google Scholar
  27. Igor C. Oliveira and Rahul Santhanam. Hardness Magnification for Natural Problems. In Symposium on Foundations of Computer Science (FOCS), pages 65-76, 2018. Google Scholar
  28. A. 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
  29. Ronen Shaltiel and Emanuele Viola. Hardness Amplification Proofs Require Majority. SIAM J. Comput., 39(7):3122-3154, 2010. Google Scholar
  30. R. Smolensky. On representations by low-degree polynomials. In FOCS, pages 130-138, 1993. Google Scholar
  31. Boris Trakhtenbrot. A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms. IEEE Ann. Hist. Comput., 6(4):384-400, October 1984. Google Scholar
  32. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact