Document Open Access Logo

On the Average-Case Complexity of MCSP and Its Variants

Authors Shuichi Hirahara, Rahul Santhanam

PDF
Thumbnail PDF

File

LIPIcs.CCC.2017.7.pdf
  • Filesize: 0.57 MB
  • 20 pages

Document Identifiers

Author Details

Shuichi Hirahara
Rahul Santhanam

Cite As Get BibTex

Shuichi Hirahara and Rahul Santhanam. On the Average-Case Complexity of MCSP and Its Variants. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CCC.2017.7

Abstract

We prove various results on the complexity of MCSP (Minimum Circuit Size Problem) and the related MKTP (Minimum Kolmogorov Time-Bounded Complexity Problem):

* We observe that under standard cryptographic assumptions, MCSP has a pseudorandom self-reduction. This is a new notion we define by relaxing the notion of a random self-reduction to allow queries to be pseudorandom rather than uniformly random. As a consequence we derive a weak form of a worst-case to average-case reduction for (a promise version of) MCSP. Our result also distinguishes MCSP from natural NP-complete problems, which are not known to have worst-case to average-case reductions. Indeed, it is known that strong forms of worst-case to average-case reductions for NP-complete problems collapse the Polynomial Hierarchy.

* We prove the first non-trivial formula size lower bounds for MCSP by showing that MCSP requires nearly quadratic-size De Morgan formulas.

* We show average-case superpolynomial size lower bounds for MKTP against AC0[p] for any prime p.

* We show the hardness of MKTP on average under assumptions that have been used in much recent work, such as Feige's assumptions, Alekhnovich's assumption and the Planted Clique conjecture. In addition, MCSP is hard under Alekhnovich's assumption. Using a version of Feige's assumption against co-nondeterministic algorithms that has been conjectured recently, we provide evidence for the first time that MKTP is not in coNP. Our results suggest that it might worthwhile to focus on the average-case hardness of MKTP and MCSP when approaching the question of whether these problems are NP-hard.

Subject Classification

Keywords
  • minimum circuit size problem
  • average-case complexity
  • circuit lower bounds
  • time-bounded Kolmogorov complexity
  • hardness

Metrics

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

References

  1. Miklós Ajtai and Michael Ben-Or. A theorem on probabilistic constant depth computations. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), pages 471-474, 1984. URL: http://dx.doi.org/10.1145/800057.808715.
  2. Michael Alekhnovich. More on average case vs approximation complexity. Computational Complexity, 20(4):755-786, 2011. URL: http://dx.doi.org/10.1007/s00037-011-0029-x.
  3. E. Allender, Joshua Grochow, and Cristopher Moore. Graph isomorphism and circuit size. Technical Report TR15-162, Electronic Colloquium on Computational Complexity, 2015. Google Scholar
  4. Eric Allender. The complexity of complexity. In Computability and Complexity - Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, pages 79-94, 2017. URL: http://dx.doi.org/10.1007/978-3-319-50062-1_6.
  5. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from random strings. SIAM J. Comput., 35(6):1467-1493, 2006. URL: http://dx.doi.org/10.1137/050628994.
  6. Eric Allender and Bireswar Das. Zero knowledge and circuit minimization. In Symposium on Mathematical Foundations of Computer Science (MFCS), pages 25-32, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44465-8_3.
  7. 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: http://dx.doi.org/10.1137/060664537.
  8. Eric Allender and Shuichi Hirahara. New insights on the (non)-hardness of circuit minimization and related problems. Electronic Colloquium on Computational Complexity (ECCC), 24:73, 2017. URL: https://eccc.weizmann.ac.il/report/2017/073.
  9. Eric Allender, Dhiraj Holden, and Valentine Kabanets. The minimum oracle circuit size problem. In Symposium on Theoretical Aspects of Computer Science (STACS), volume 30 of LIPIcs, pages 21-33, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.21.
  10. Eric Allender, Michael Koucky, Detlef Ronneburger, and Sambuddha Roy. The pervasive reach of resource-bounded kolmogorov complexity in computational complexity theory. Journal of Computer and System Sciences, 77:14-40, 2010. Google Scholar
  11. Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7(4):567-583, 1986. URL: http://dx.doi.org/10.1016/0196-6774(86)90019-2.
  12. Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for NP problems. SIAM Journal on Computing, 36(4):1119-1159, 2006. Google Scholar
  13. Andrej Brodnik and J. Ian Munro. Membership in constant time and almost-minimum space. SIAM J. Comput., 28(5):1627-1640, 1999. URL: http://dx.doi.org/10.1137/S0097539795294165.
  14. Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola. On beating the hybrid argument. Theory of Computing, 9:809-843, 2013. URL: http://dx.doi.org/10.4086/toc.2013.v009a026.
  15. Uriel Feige. Relations between average case complexity and approximation complexity. In Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC), pages 534-543, 2002. URL: http://dx.doi.org/10.1145/509907.509985.
  16. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. J. ACM, 33(4):792-807, 1986. URL: http://dx.doi.org/10.1145/6490.6503.
  17. Johan Håstad. The shrinkage exponent of de morgan formulas is 2. SIAM J. Comput., 27(1):48-64, 1998. URL: http://dx.doi.org/10.1137/S0097539794261556.
  18. Shuichi Hirahara and Osamu Watanabe. Limits of minimum circuit size problem as oracle. In Conference on Computational Complexity (CCC), volume 50 of LIPIcs, pages 18:1-18:20, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.18.
  19. John M. 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), volume 45 of LIPIcs, pages 236-245, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2015.236.
  20. Russell Impagliazzo, Raghu Meka, and David Zuckerman. Pseudorandomness from shrinkage. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 111-119, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.78.
  21. Yuval Ishai and Eyal Kushilevitz. Randomizing polynomials: A new representation with applications to round-efficient secure computation. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), pages 294-304, 2000. URL: http://dx.doi.org/10.1109/SFCS.2000.892118.
  22. Yuval Ishai and Eyal Kushilevitz. Perfect constant-round secure computation via perfect randomizing polynomials. In Proceedings of Automata, Languages and Programming, 29th International Colloquium (ICALP), pages 244-256, 2002. URL: http://dx.doi.org/10.1007/3-540-45465-9_22.
  23. Mark Jerrum. Large cliques elude the metropolis process. Random Structures and Algorithms, 3:347-359, 1992. Google Scholar
  24. Valentine Kabanets and Jin-Yi Cai. Circuit minimization problem. In Symposium on Theory of Computing (STOC), pages 73-79, 2000. URL: http://dx.doi.org/10.1145/335305.335314.
  25. Ilan Komargodski, Ran Raz, and Avishay Tal. Improved average-case lower bounds for DeMorgan formula size. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 588-597, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.69.
  26. Ludek Kucera. Expected complexity of graph partitioning problems. Discrete Applied Mathematics, 57(2-3):193-212, 1995. Google Scholar
  27. Cody D. Murray and Richard Ryan Williams. On the (non) NP-hardness of computing circuit complexity. In Conference on Computational Complexity (CCC), volume 33 of LIPIcs, pages 365-380, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.365.
  28. Mihai Patrascu. Succincter. In In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 305-313, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.83.
  29. Alexander 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. URL: http://dx.doi.org/10.1007/BF01137685.
  30. Alexander A. Razborov and Steven Rudich. Natural proofs. J. Comput. Syst. Sci., 55(1):24-35, 1997. URL: http://dx.doi.org/10.1006/jcss.1997.1494.
  31. Steven Rudich. Super-bits, demi-bits, and NP/qpoly-natural proofs. In Proceedings of Randomization and Approximation Techniques in Computer Science (RANDOM), pages 85-93, 1997. URL: http://dx.doi.org/10.1007/3-540-63248-4_8.
  32. Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Alfred V. Aho, editor, STOC, pages 77-82. ACM, 1987. URL: http://dblp.uni-trier.de/db/conf/stoc/stoc87.html#Smolensky87.
  33. Philip M Spira. On time-hardware complexity tradeoffs for boolean functions. In Proceedings of the 4th Hawaii Symposium on System Sciences, pages 525-527, 1971. Google Scholar
  34. Boris Trakhtenbrot. A survey of russian approaches to perebor (brute-force search) algorithms. IEEE Annals of the History of Computing, 6(4):384-400, 1984. Google Scholar
  35. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. SIAM J. Comput., 42(3):1218-1244, 2013. URL: http://dx.doi.org/10.1137/10080703X.
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