Document Open Access Logo

On Oracles and Algorithmic Methods for Proving Lower Bounds

Authors Nikhil Vyas , Ryan Williams

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.99.pdf
  • Filesize: 0.92 MB
  • 26 pages

Document Identifiers

Author Details

Nikhil Vyas
  • Harvard University, Cambridge, MA, USA
Ryan Williams
  • MIT CSAIL and EECS, Cambridge, MA, USA

Funding

  • Vyas, Nikhil: This work was done while the author was a PhD student at MIT, supported by NSF CCF-1909429 and CCF-2127597.
  • Williams, Ryan: Supported by NSF CCF-1909429 and NSF CCF-2127597.

Acknowledgements

We thank Dylan McKay and Brynmor Chapman for helpful discussions on the missing string problem.

Cite AsGet BibTex

Nikhil Vyas and Ryan Williams. On Oracles and Algorithmic Methods for Proving Lower Bounds. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 99:1-99:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.99

Abstract

This paper studies the interaction of oracles with algorithmic approaches to proving circuit complexity lower bounds, establishing new results on two different kinds of questions. 1) We revisit some prominent open questions in circuit lower bounds, and provide a clean way of viewing them as circuit upper bound questions. Let Missing-String be the (total) search problem of producing a string that does not appear in a given list L containing M bit-strings of length N, where M < 2ⁿ. We show in a generic way how algorithms and uniform circuits (from restricted classes) for Missing-String imply complexity lower bounds (and in some cases, the converse holds as well). We give a local algorithm for Missing-String, which can compute any desired output bit making very few probes into the input, when the number of strings M is small enough. We apply this to prove a new nearly-optimal (up to oracles) time hierarchy theorem with advice. We show that the problem of constructing restricted uniform circuits for Missing-String is essentially equivalent to constructing functions without small non-uniform circuits, in a relativizing way. For example, we prove that small uniform depth-3 circuits for Missing-String would imply exponential circuit lower bounds for Σ₂ EXP, and depth-3 lower bounds for Missing-String would imply non-trivial circuits (relative to an oracle) for Σ₂ EXP problems. Both conclusions are longstanding open problems in circuit complexity. 2) It has been known since Impagliazzo, Kabanets, and Wigderson [JCSS 2002] that generic derandomizations improving subexponentially over exhaustive search would imply lower bounds such as NEXP ̸ ⊂ 𝖯/poly. Williams [SICOMP 2013] showed that Circuit-SAT algorithms running barely faster than exhaustive search would imply similar lower bounds. The known proofs of such results do not relativize (they use techniques from interactive proofs/PCPs). However, it has remained open whether there is an oracle under which the generic implications from circuit-analysis algorithms to circuit lower bounds fail. Building on an oracle of Fortnow, we construct an oracle relative to which the circuit approximation probability problem (CAPP) is in 𝖯, yet EXP^{NP} has polynomial-size circuits. We construct an oracle relative to which SAT can be solved in "half-exponential" time, yet exponential time (EXP) has polynomial-size circuits. Improving EXP to NEXP would give an oracle relative to which Σ₂ 𝖤 has "half-exponential" size circuits, which is open. (Recall it is known that Σ₂ 𝖤 is not in "sub-half-exponential" size, and the proof relativizes.) Moreover, the running time of the SAT algorithm cannot be improved: relative to all oracles, if SAT is in "sub-half-exponential" time then EXP does not have polynomial-size circuits.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Complexity classes
Keywords
  • oracles
  • relativization
  • circuit complexity
  • missing string
  • exponential hierarchy

Metrics

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

References

  1. Scott Aaronson. "Closed-form" functions with half-exponential growth. Math Overflow, https://web.archive.org/web/20210514235809/https://mathoverflow.net/questions/45477/closed-form-functions-with-half-exponential-growth, 2010.
  2. Scott Aaronson. G. phi. fo. fum. Shtetl-Optimized, URL: https://web.archive.org/web/20220221023022/https://scottaaronson.blog/?p=2521, 2015.
  3. Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John M. Hitchcock, and Dieter van Melkebeek. A note on exponential circuit lower bounds from derandomizing arthur-merlin games. Electron. Colloquium Comput. Complex., page 174, 2010. URL: https://eccc.weizmann.ac.il/report/2010/174, URL: http://arxiv.org/abs/TR10-174.
  4. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. ACM TOCT, 1, 2009. Google Scholar
  5. Dana Angluin. On counting problems and the polynomial-time hierarchy. Theor. Comput. Sci., 12:161-173, 1980. URL: https://doi.org/10.1016/0304-3975(80)90027-4.
  6. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
  7. Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor Carboni Oliveira, and Aarthi Sundaram. Quantum learning algorithms imply circuit lower bounds. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 562-573, 2021. Google Scholar
  8. Baris Aydinlioglu and Eric Bach. Affine relativization: Unifying the algebrization and relativization barriers. ACM Trans. Comput. Theory, 10(1):1:1-1:67, 2018. URL: https://doi.org/10.1145/3170704.
  9. Baris Aydinlioglu, Dan Gutfreund, John M. Hitchcock, and Akinori Kawachi. Derandomizing arthur-merlin games and approximate counting implies exponential-size lower bounds. Comput. Complex., 20(2):329-366, 2011. URL: https://doi.org/10.1007/s00037-011-0010-8.
  10. Baris Aydinlioglu and Dieter van Melkebeek. Nondeterministic circuit lower bounds from mildly derandomizing arthur-merlin games. Comput. Complex., 26(1):79-118, 2017. URL: https://doi.org/10.1007/s00037-014-0095-y.
  11. Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P =? NP question. SIAM J. Comput., 4(4):431-442, 1975. Google Scholar
  12. J. M. Barzdiņš and R. V. Freivalds. On the prediction of general recursive functions (in russian). Doklady Akademii Nauk, 206(3):521-524, 1972. Google Scholar
  13. Richard Bird. Pearls of Functional Algorithm Design. Cambridge University Press, 2010. URL: http://www.cambridge.org/gb/knowledge/isbn/item5600469.
  14. Harry Buhrman and Lance Fortnow. One-sided versus two-sided error in probabilistic computation. In STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999, Proceedings, volume 1563 of Lecture Notes in Computer Science, pages 100-109, 1999. URL: https://doi.org/10.1007/3-540-49116-3_9.
  15. Harry Buhrman, Lance Fortnow, and Thomas Thierauf. Nonrelativizing separations. In Proceedings of the 13th Annual IEEE Conference on Computational Complexity, Buffalo, New York, USA, June 15-18, 1998, pages 8-12, 1998. URL: https://doi.org/10.1109/CCC.1998.694585.
  16. Lance Fortnow. Comparing notions of full derandomization. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pages 28-34, 2001. URL: https://doi.org/10.1109/CCC.2001.933869.
  17. Lance Fortnow and Rahul Santhanam. Time hierarchies: A survey. Electron. Colloquium Comput. Complex., TR07-004, 2007. Google Scholar
  18. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. Google Scholar
  19. Oded Goldreich. On promise problems: A survey. In Theoretical Computer Science, Essays in Memory of Shimon Even, volume 3895 of Lecture Notes in Computer Science, pages 254-290, 2006. URL: https://doi.org/10.1007/11685654_12.
  20. Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. An axiomatic approach to algebrization. In STOC, pages 695-704, 2009. URL: https://doi.org/10.1145/1536414.1536509.
  21. 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.
  22. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In STOC, pages 220-229, 1997. Google Scholar
  23. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1-46, 2004. URL: https://doi.org/10.1007/s00037-004-0182-6.
  24. Ravi Kannan. Circuit-size lower bounds and non-reducibility to sparse sets. Inf. Control., 55(1-3):40-56, 1982. Preliminary version in FOCS'81. URL: https://doi.org/10.1016/S0019-9958(82)90382-5.
  25. Ravi Kannan, H. Venkateswaran, V. Vinay, and Andrew Chi-Chih Yao. A circuit-based proof of Toda’s theorem. Inf. Comput., 104(2):271-276, 1993. URL: https://doi.org/10.1006/inco.1993.1033.
  26. Richard Karp and Richard Lipton. Turing machines that take advice. L'Enseignement Mathématique, 28(2):191-209, 1982. Google Scholar
  27. Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos H. Papadimitriou. Total functions in the polynomial hierarchy. In 12th Innovations in Theoretical Computer Science Conference, ITCS, volume 185 of LIPIcs, pages 44:1-44:18, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.44.
  28. Adam Klivans and Dieter van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial hierarchy collapses. SIAM J. Comput., 31(5):1501-1526, 2002. Google Scholar
  29. Oliver Korten. The hardest explicit construction. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 433-444, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00051.
  30. Clemens Lautemann. BPP and the polynomial hierarchy. Inf. Process. Lett., 17(4):215-217, 1983. URL: https://doi.org/10.1016/0020-0190(83)90044-3.
  31. Peter Bro Miltersen, N. V. Vinodchandran, and Osamu Watanabe. Super-polynomial versus half-exponential circuit size in the exponential hierarchy. In Computing and Combinatorics, 5th Annual International Conference, COCOON '99, Tokyo, Japan, July 26-28, 1999, Proceedings, volume 1627 of Lecture Notes in Computer Science, pages 210-220, 1999. URL: https://doi.org/10.1007/3-540-48686-0_21.
  32. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. Google Scholar
  33. Alexander Razborov and Steven Rudich. Natural proofs. J. Comput. Syst. Sci., 55(1):24-35, 1997. Google Scholar
  34. Hanlin Ren, Rahul Santhanam, and Zhikun Wang. On the Range Avoidance problem for circuits. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 (to appear), 2022. Google Scholar
  35. Walter L. Ruzzo. On uniform circuit complexity. J. Comput. Syst. Sci., 22(3):365-383, 1981. URL: https://doi.org/10.1016/0022-0000(81)90038-6.
  36. Larry J. Stockmeyer and Albert R. Meyer. Cosmological lower bound on the circuit complexity of a small problem in logic. J. ACM, 49(6):753-784, 2002. Google Scholar
  37. Larry Joseph Stockmeyer. The complexity of decision problems in automata theory and logic. PhD thesis, Massachusetts Institute of Technology, Department of Electrical Engineering, https://dspace.mit.edu/handle/1721.1/15540, 1974.
  38. Iannis Tourlakis. Time-space tradeoffs for SAT on nonuniform machines. J. Comput. Syst. Sci., 63(2):268-287, 2001. Google Scholar
  39. H. Venkateswaran. Circuit definitions of nondeterministic complexity classes. SIAM J. Comput., 21(4):655-670, 1992. URL: https://doi.org/10.1137/0221040.
  40. V. Vinay, H. Venkateswaran, and C. E. Veni Madhavan. Circuits, pebbling and expressibility. In Proceedings: Fifth Annual Structure in Complexity Theory Conference, pages 223-230, 1990. URL: https://doi.org/10.1109/SCT.1990.113970.
  41. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. SIAM Journal on Computing, 42(3):1218-1244, 2013. Google Scholar
  42. Ryan Williams. Nonuniform ACC circuit lower bounds. J. ACM, 61(1):2:1-2:32, 2014. URL: https://doi.org/10.1145/2559903.
  43. Christopher B. Wilson. Relativized circuit complexity. J. Comput. Syst. Sci., 31(2):169-181, 1985. URL: https://doi.org/10.1016/0022-0000(85)90040-6.
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