Document Open Access Logo

One-Tape Turing Machine and Branching Program Lower Bounds for MCSP

Authors Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida

PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.23.pdf
  • Filesize: 0.75 MB
  • 19 pages

Document Identifiers

Author Details

Mahdi Cheraghchi
  • Department of EECS, University of Michigan, Ann Arbor, MI, USA
Shuichi Hirahara
  • National Institute of Informatics, Tokyo, Japan
Dimitrios Myrisiotis
  • Department of Computing, Imperial College London, London, UK
Yuichi Yoshida
  • National Institute of Informatics, Tokyo, Japan

Funding

  • Cheraghchi, Mahdi: M. Cheraghchi’s research is supported in part by the NSF award CCF-2006455.

Acknowledgements

We would like to express our gratitude to Emanuele Viola and Osamu Watanabe for bringing to our attention the works by Kalyanasundaram and Schnitger [Bala Kalyanasundaram and Georg Schnitger, 1992] and Watanabe [Osamu Watanabe, 1983], respectively, and for helpful discussions. In particular, we thank Emanuele Viola for explaining to us his works [Elad Haramaty et al., 2018; Emanuele Viola, 2019]. We thank Rahul Santhanam for pointing out that {N}ečiporuk’s method can be applied to not only MKtP but also MKTP. We thank Chin Ho Lee for answering our questions regarding his work [Chin Ho Lee, 2019]. We thank Paul Beame for bringing his work [Paul Beame et al., 2016] to our attention. We thank Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira, and Ninad Rajgopal for illuminating discussions. Finally, we would like to thank the anonymous reviewers for their constructive feedback.

Cite As Get BibTex

Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, and Yuichi Yoshida. One-Tape Turing Machine and Branching Program Lower Bounds for MCSP. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.STACS.2021.23

Abstract

For a size parameter s: ℕ → ℕ, the Minimum Circuit Size Problem (denoted by MCSP[s(n)]) is the problem of deciding whether the minimum circuit size of a given function f : {0,1}ⁿ → {0,1} (represented by a string of length N : = 2ⁿ) is at most a threshold s(n). A recent line of work exhibited "hardness magnification" phenomena for MCSP: A very weak lower bound for MCSP implies a breakthrough result in complexity theory. For example, McKay, Murray, and Williams (STOC 2019) implicitly showed that, for some constant μ₁ > 0, if MCSP[2^{μ₁⋅ n}] cannot be computed by a one-tape Turing machine (with an additional one-way read-only input tape) running in time N^{1.01}, then P≠NP.
In this paper, we present the following new lower bounds against one-tape Turing machines and branching programs:  
1) A randomized two-sided error one-tape Turing machine (with an additional one-way read-only input tape) cannot compute MCSP[2^{μ₂⋅n}] in time N^{1.99}, for some constant μ₂ > μ₁. 
2) A non-deterministic (or parity) branching program of size o(N^{1.5}/log N) cannot compute MKTP, which is a time-bounded Kolmogorov complexity analogue of MCSP. This is shown by directly applying the Nečiporuk method to MKTP, which previously appeared to be difficult. 
3) The size of any non-deterministic, co-non-deterministic, or parity branching program computing MCSP is at least N^{1.5-o(1)}.  These results are the first non-trivial lower bounds for MCSP and MKTP against one-tape Turing machines and non-deterministic branching programs, and essentially match the best-known lower bounds for any explicit functions against these computational models.
The first result is based on recent constructions of pseudorandom generators for read-once oblivious branching programs (ROBPs) and combinatorial rectangles (Forbes and Kelley, FOCS 2018; Viola 2019). En route, we obtain several related results:  
1) There exists a (local) hitting set generator with seed length Õ(√N) secure against read-once polynomial-size non-deterministic branching programs on N-bit inputs. 
2) Any read-once co-non-deterministic branching program computing MCSP must have size at least 2^Ω̃(N).

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Minimum Circuit Size Problem
  • Kolmogorov Complexity
  • One-Tape Turing Machines
  • Branching Programs
  • Lower Bounds
  • Pseudorandom Generators
  • Hitting Set Generators

Metrics

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

Related Versions

References

  1. 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
  2. Eric Allender and Shuichi Hirahara. New insights on the (non-)hardness of circuit minimization and related problems. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 54:1-54:14, 2017. Google Scholar
  3. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. ACM, 57(3):14:1-14:36, 2010. Google Scholar
  4. Eric Allender, Michal Koucký, Detlef Ronneburger, and Sambuddha Roy. The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. J. Comput. Syst. Sci., 77(1):14-40, 2011. Google Scholar
  5. Alexander E. Andreev, Juri L. Baskakov, Andrea E. F. Clementi, and José D. P. Rolim. Small pseudo-random sets yield hard functions: New tight explicit lower bounds for branching programs. In Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP), pages 179-189, 1999. Google Scholar
  6. Paul Beame, Nathan Grosshans, Pierre McKenzie, and Luc Segoufin. Nondeterminism and an abstract formulation of Nečiporuk’s lower bound method. ACM Trans. Comput. Theory, 9(1):5:1-5:34, 2016. Google Scholar
  7. Allan Borodin, Alexander A. Razborov, and Roman Smolensky. On lower bounds for read-k-times branching programs. Computational Complexity, 3:1-18, 1993. Google Scholar
  8. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning algorithms from natural proofs. In Proceedings of the 31st Conference on Computational Complexity (CCC), pages 10:1-10:24, 2016. Google Scholar
  9. 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 2020, January 12-14, 2020, Seattle, Washington, USA, pages 70:1-70:48, 2020. Google Scholar
  10. Lijie Chen, Ce Jin, and R. Ryan Williams. Hardness magnification for all sparse NP languages. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1240-1255, 2019. Google Scholar
  11. Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, and Dimitrios Myrisiotis. Circuit lower bounds for MCSP from local pseudorandom generators. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 39:1-39:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  12. Stephen A. Cook and Robert A. Reckhow. Time-bounded random access machines. In Patrick C. Fischer, H. Paul Zeiger, Jeffrey D. Ullman, and Arnold L. Rosenberg, editors, Proceedings of the 4th Annual ACM Symposium on Theory of Computing, May 1-3, 1972, Denver, Colorado, USA, pages 73-80. ACM, 1972. Google Scholar
  13. Michael A. Forbes and Zander Kelley. Pseudorandom generators for read-once branching programs, in any order. In Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 946-955, 2018. Google Scholar
  14. Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal. AC⁰[p] lower bounds against MCSP via the coin problem. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 66:1-66:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  15. Elad Haramaty, Chin Ho Lee, and Emanuele Viola. Bounded independence plus noise fools products. SIAM J. Comput., 47(2):493-523, 2018. Google Scholar
  16. Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364-1396, 1999. Google Scholar
  17. F. C. Hennie. One-tape, off-line turing machine computations. Inf. Control., 8(6):553-578, 1965. Google Scholar
  18. Shuichi Hirahara. Non-black-box worst-case to average-case reductions within NP. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 247-258, 2018. Google Scholar
  19. Shuichi Hirahara. Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions, 2020. Manuscript. Google Scholar
  20. Shuichi Hirahara and Rahul Santhanam. On the average-case complexity of MCSP and its variants. In Proceedings of the 32nd Computational Complexity Conference (CCC), pages 7:1-7:20, 2017. Google Scholar
  21. Shuichi Hirahara and Osamu Watanabe. Limits of minimum circuit size problem as oracle. In Proceedings of the 31st Conference on Computational Complexity (CCC), pages 18:1-18:20, 2016. Google Scholar
  22. John M. Hitchcock and Aduri Pavan. On the NP-completeness of the minimum circuit size problem. In Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS), pages 236-245, 2015. Google Scholar
  23. Russell Impagliazzo, Raghu Meka, and David Zuckerman. Pseudorandomness from Shrinkage. J. ACM, 66(2):11:1-11:16, 2019. Google Scholar
  24. Stasys Jukna. Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and combinatorics. Springer, 2012. Google Scholar
  25. Valentine Kabanets and Jin-yi Cai. Circuit minimization problem. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), pages 73-79, 2000. Google Scholar
  26. Bala Kalyanasundaram and Georg Schnitger. Communication complexity and lower bounds for sequential computation. In Informatik, Festschrift zum 60. Geburtstag von Günter Hotz, pages 253-268. Teubner / Springer, 1992. Google Scholar
  27. Chin Ho Lee. Fourier bounds and pseudorandom generators for product tests. In Proceedings of the 34th Computational Complexity Conference (CCC), pages 7:1-7:25, 2019. Google Scholar
  28. Wolfgang Maass. Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines (extended abstract). In Proceedings of the 16th Annual ACM Symposium on Theory of Computing (STOC), pages 401-408, 1984. Google Scholar
  29. Wolfgang Maass and Amir Schorr. Speed-up of Turing machines with one work tape and a two-way input tape. SIAM J. Comput., 16(1):195-202, 1987. Google Scholar
  30. 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 Symposium on Theory of Computing (STOC), pages 1215-1225, 2019. Google Scholar
  31. Cody D. Murray and Richard Ryan Williams. On the (non) NP-hardness of computing circuit complexity. In Proceedings of the 30th Conference on Computational Complexity (CCC), pages 365-380, 2015. Google Scholar
  32. E.I. Nečiporuk. On a Boolean function. Doklady Akademii Nauk SSSR, 169(4):765-766, 1966. English translation in Soviet Mathematics Doklady. Google Scholar
  33. Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam. Hardness magnification near state-of-the-art lower bounds. In Proceedings of the 34th Computational Complexity Conference (CCC), pages 27:1-27:29, 2019. Google Scholar
  34. Igor Carboni Oliveira and Rahul Santhanam. Hardness magnification for natural problems. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 65-76, 2018. Google Scholar
  35. Alexander A. Razborov and Steven Rudich. Natural proofs. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), pages 204-213, 1994. Google Scholar
  36. Claude E. Shannon. The synthesis of two-terminal switching circuits. Bell Systems Technical Journal, 28:59-98, 1949. Google Scholar
  37. Dieter van Melkebeek and Ran Raz. A time lower bound for satisfiability. In Josep Díaz, Juhani Karhumäki, Arto Lepistö, and Donald Sannella, editors, Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings, volume 3142 of Lecture Notes in Computer Science, pages 971-982. Springer, 2004. Google Scholar
  38. Emanuele Viola. Pseudorandom bits and lower bounds for randomized Turing machines. Electronic Colloquium on Computational Complexity (ECCC), 26:51, 2019. Google Scholar
  39. Osamu Watanabe. The time-precision tradeoff problem on on-line probabilistic Turing machines. Theor. Comput. Sci., 24:105-117, 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