Document Open Access Logo

Hardness Magnification near State-Of-The-Art Lower Bounds

Authors Igor Carboni Oliveira, Ján Pich, Rahul Santhanam

PDF
Thumbnail PDF

File

LIPIcs.CCC.2019.27.pdf
  • Filesize: 0.75 MB
  • 29 pages

Document Identifiers

Author Details

Igor Carboni Oliveira
  • Department of Computer Science, University of Oxford, UK
Ján Pich
  • Department of Computer Science, University of Oxford, UK
Rahul Santhanam
  • Department of Computer Science, University of Oxford, UK

Funding

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 and by the Austrian Science Fund (FWF) under project number P 28699.

Acknowledgements

We thank Avishay Tal for bringing [Avishay Tal, 2016] to our attention in connection to the problem of proving lower bounds against U_2-Formula-oplus. We are also grateful to Jan Krajíček for discussions related to hardness magnification.

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 27:1-27:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.CCC.2019.27

Abstract

This work continues the development of hardness magnification. The latter proposes a new strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be successful. 
We consider gap versions of the meta-computational problems MKtP and MCSP, where one needs to distinguish instances (strings or truth-tables) of complexity <= s_1(N) from instances of complexity >= s_2(N), and N = 2^n denotes the input length. In MCSP, complexity is measured by circuit size, while in MKtP one considers Levin’s notion of time-bounded Kolmogorov complexity. (In our results, the parameters s_1(N) and s_2(N) are asymptotically quite close, and the problems almost coincide with their standard formulations without a gap.) We establish that for Gap-MKtP[s_1,s_2] and Gap-MCSP[s_1,s_2], a marginal improvement over the state-of-the-art in unconditional lower bounds in a variety of computational models would imply explicit super-polynomial lower bounds.

Theorem. There exists a universal constant c >= 1 for which the following hold. If there exists epsilon > 0 such that for every small enough beta > 0 
(1) Gap-MCSP[2^{beta n}/c n, 2^{beta n}] !in Circuit[N^{1 + epsilon}], then NP !subseteq Circuit[poly]. 
(2) Gap-MKtP[2^{beta n}, 2^{beta n} + cn] !in TC^0[N^{1 + epsilon}], then EXP !subseteq TC^0[poly]. 
(3) Gap-MKtP[2^{beta n}, 2^{beta n} + cn] !in B_2-Formula[N^{2 + epsilon}], then EXP !subseteq Formula[poly]. 
(4) Gap-MKtP[2^{beta n}, 2^{beta n} + cn] !in U_2-Formula[N^{3 + epsilon}], then EXP !subseteq Formula[poly]. 
(5) Gap-MKtP[2^{beta n}, 2^{beta n} + cn] !in BP[N^{2 + epsilon}], then EXP !subseteq BP[poly]. 
(6) Gap-MKtP[2^{beta n}, 2^{beta n} + cn] !in (AC^0[6])[N^{1 + epsilon}], then EXP !subseteq AC^0[6]. 
 These results are complemented by lower bounds for Gap-MCSP and Gap-MKtP against different models. For instance, the lower bound assumed in (1) holds for U_2-formulas of near-quadratic size, and lower bounds similar to (3)-(5) hold for various regimes of parameters.
We also identify a natural computational model under which the hardness magnification threshold for Gap-MKtP lies below existing lower bounds: U_2-formulas that can compute parity functions at the leaves (instead of just literals). As a consequence, if one managed to adapt the existing lower bound techniques against such formulas to work with Gap-MKtP, then EXP !subseteq NC^1 would follow via hardness magnification.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Circuit Complexity
  • Minimum Circuit Size Problem
  • Kolmogorov Complexity

Metrics

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

Related Versions

References

  1. Scott Aaronson. P= ^?NP. Electronic Colloquium on Computational Complexity (ECCC), 24:4, 2017. URL: https://eccc.weizmann.ac.il/report/2017/004.
  2. Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, and Avi Wigderson. Pseudorandom generators in propositional proof complexity. SIAM Journal of Computing, 34(1):67-88, 2004. Google Scholar
  3. Eric Allender. When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity. In Foundations of Software Technology and Theoretical Computer Science FSTTCS, pages 1-15, 2001. URL: https://doi.org/10.1007/3-540-45294-X_1.
  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. Google Scholar
  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. Google Scholar
  6. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. ACM, 57(3):14:1-14:36, 2010. Google Scholar
  7. Andrej Bogdanov. Small-bias require large formulas. In International Colloquium on Automata, Languages, and Programming (ICALP), 2018. Google Scholar
  8. Ravi B. Boppana and Michael Sipser. The Complexity of Finite Functions. In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, pages 757-804. The MIT Press/Elsevier, 1990. Google Scholar
  9. Harry Buhrman, Lance Fortnow, and Thomas Thierauf. Nonrelativizing Separations. In Conference on Computational Complexity (CCC), pages 8-12, 1998. URL: https://doi.org/10.1109/CCC.1998.694585.
  10. Jin-yi Cai. 𝖲^p₂ is subset of ZPP^NP. J. Comput. Syst. Sci., 73(1):25-35, 2007. URL: https://doi.org/10.1016/j.jcss.2003.07.015.
  11. Marco Carmosino, Russell Impagliazzo, Shachar Lovett, and Ivan Mihajlin. Hardness Amplification for Non-Commutative Arithmetic Circuits. In Computational Complexity Conference (CCC), 2018. Google Scholar
  12. 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.
  13. Irit Dinur and Or Meir. Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. In Conference on Computational Complexity (CCC), pages 3:1-3:51, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.3.
  14. Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov. A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. In Symposium on Foundations of Computer Science (FOCS), pages 89-98, 2016. Google Scholar
  15. Oded Goldreich. Computational Complexity - A Conceptual Perspective. Cambridge University Press, 2008. Google Scholar
  16. 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.
  17. 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. Google Scholar
  18. Pavel Hrubeš, Avi Wigderson, and Amir Yehudayoff. Non-commutative circuits and the sum-of-squares problem. Journal of the American Mathematical Society, 24(3):871-898, 2011. Google Scholar
  19. Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich. The power of natural properties as oracles. In Computational Complexity Conference (CCC), 2018. Google Scholar
  20. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In search of an easy witness: exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci., 65(4):672-694, 2002. URL: https://doi.org/10.1016/S0022-0000(02)00024-7.
  21. Russell Impagliazzo, Raghu Meka, and David Zuckerman. Pseudorandomness from Shrinkage. In Symposium on Foundations of Computer Science (FOCS), pages 111-119, 2012. Google Scholar
  22. Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks. Size-Depth Tradeoffs for Threshold Circuits. SIAM J. Comput., 26(3):693-707, 1997. URL: https://doi.org/10.1137/S0097539792282965.
  23. Kazuo Iwama and Hiroki Morizumi. An Explicit Lower Bound of 5n - o(n) for Boolean Circuits. In Symposium on Mathematical Foundations of Computer Science (MFCS), pages 353-364, 2002. Google Scholar
  24. Stasys Jukna. Boolean Function Complexity - Advances and Frontiers. Springer, 2012. Google Scholar
  25. 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.
  26. Valentine Kabanets and Jin-yi Cai. Circuit minimization problem. In Symposium on Theory of Computing (STOC), pages 73-79, 2000. URL: https://doi.org/10.1145/335305.335314.
  27. Daniel M. Kane and Ryan Williams. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In Symposium on Theory of Computing (STOC), pages 633-643, 2016. URL: https://doi.org/10.1145/2897518.2897636.
  28. Ilan Komargodski, Ran Raz, and Avishay Tal. Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound. SIAM J. Comput., 46(1):37-57, 2017. URL: https://doi.org/10.1137/15M1048045.
  29. Jan Krajíček. Extensions of models of PV. In ASL/Springer Series - Lecture Notes in Logic - Proceedings of the Logic Colloquium, 1995. Google Scholar
  30. Jan Krajíček. On the weak pigeonhole principle. Fundamenta Mathematicae, 170(1-3):123-140, 2001. Google Scholar
  31. Jan Krajíček. Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds. Journal of Symbolic Logic, 69(1):265-286, 2004. Google Scholar
  32. Leonid Levin. Randomness Conservation Inequalities; Information and Independence in Mathematical Theories. Information and Control, 61:15-37, 1984. Google Scholar
  33. Richard J. Lipton and Ryan Williams. Amplifying circuit lower bounds against polynomial time, with applications. Computational Complexity, 22(2):311-343, 2013. Google Scholar
  34. Richard J. Lipton and Neal E. Young. Simple strategies for large zero-sum games with applications to complexity theory. In Symposium on Theory of Computing (STOC), pages 734-740, 1994. URL: https://doi.org/10.1145/195058.195447.
  35. 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
  36. Eric Miles and Emanuele Viola. Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs. J. ACM, 62(6):46:1-46:29, 2015. 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. Google Scholar
  38. Cody Murray and R. Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP. In Symposium on Theory of Computing (STOC), pages 890-901, 2018. URL: https://doi.org/10.1145/3188745.3188910.
  39. È. Nec̆iporuk. On a boolean function. Doklady of the Academy of the USSR, 169(4):765-766, 1966. Google Scholar
  40. 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.
  41. 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.
  42. Ján Pich. Complexity Theory in Feasible Mathematics. PhD thesis, Charles University in Prague, 2014. Google Scholar
  43. Ján Pich. Circuit lower bounds in bounded arithmetics. Annals of Pure and Applied Logic, 166(1), 2015. Google Scholar
  44. Alexander A. Razborov. Lower Bounds for Deterministic and Nondeterministic Branching Programs. In Symposium on Fundamentals of Computation Theory (FCT), pages 47-60, 1991. Google Scholar
  45. Alexander A. Razborov. On provably disjoint NP-pairs. Basic Research in Computer Science Center, 1994. Google Scholar
  46. Alexander A. Razborov. Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic. Izvestiya of Russian Academy of Science,, 59:201-224, 1995. Google Scholar
  47. Alexander A. Razborov. Pseudorandom generators hard for k-DNF resolution and polynomial calculus. Annals of Mathematics, 182(2):415-472, 2015. Google Scholar
  48. Alexander A. Razborov and Steven Rudich. Natural Proofs. J. Comput. Syst. Sci., 55(1):24-35, 1997. Google Scholar
  49. Rahul Santhanam. Circuit Lower Bounds for Merlin-Arthur Classes. SIAM J. Comput., 39(3):1038-1061, 2009. URL: https://doi.org/10.1137/070702680.
  50. 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.
  51. Daniel A. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Trans. Information Theory, 42(6):1723-1731, 1996. URL: https://doi.org/10.1109/18.556668.
  52. Aravind Srinivasan. On the approximability of clique and related maximization problems. J. Comput. Syst. Sci., 67(3):633-651, 2003. Google Scholar
  53. Larry J. Stockmeyer. The Complexity of Approximate Counting (Preliminary Version). In Symposium on Theory of Computing (STOC), pages 118-126, 1983. Google Scholar
  54. Avishay Tal. Shrinkage of De Morgan Formulae by Spectral Techniques. In Symposium on Foundations of Computer Science (FOCS), pages 551-560, 2014. Google Scholar
  55. Avishay Tal. The Bipartite Formula Complexity of Inner-Product is Quadratic. Electronic Colloquium on Computational Complexity (ECCC), 23:181, 2016. Google Scholar
  56. Roei Tell. Quantified Derandomization of Linear Threshold Circuits. In Symposium on Theory of Computing (STOC), 2018. Google Scholar
  57. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. Google Scholar
  58. Ingo Wegener. The complexity of Boolean functions. Wiley, 1987. Google Scholar
  59. Ryan Williams. Nonuniform ACC Circuit Lower Bounds. J. ACM, 61(1):2:1-2:32, 2014. URL: https://doi.org/10.1145/2559903.
  60. Ryan Williams. Natural Proofs versus Derandomization. SIAM J. Comput., 45(2):497-529, 2016. URL: https://doi.org/10.1137/130938219.
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