Cheraghchi, Mahdi ;
Hirahara, Shuichi ;
Myrisiotis, Dimitrios ;
Yoshida, Yuichi
OneTape Turing Machine and Branching Program Lower Bounds for MCSP
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 onetape Turing machine (with an additional oneway readonly input tape) running in time N^{1.01}, then P≠NP.
In this paper, we present the following new lower bounds against onetape Turing machines and branching programs:
1) A randomized twosided error onetape Turing machine (with an additional oneway readonly input tape) cannot compute MCSP[2^{μ₂⋅n}] in time N^{1.99}, for some constant μ₂ > μ₁.
2) A nondeterministic (or parity) branching program of size o(N^{1.5}/log N) cannot compute MKTP, which is a timebounded 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 nondeterministic, conondeterministic, or parity branching program computing MCSP is at least N^{1.5o(1)}. These results are the first nontrivial lower bounds for MCSP and MKTP against onetape Turing machines and nondeterministic branching programs, and essentially match the bestknown lower bounds for any explicit functions against these computational models.
The first result is based on recent constructions of pseudorandom generators for readonce 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 readonce polynomialsize nondeterministic branching programs on Nbit inputs.
2) Any readonce conondeterministic branching program computing MCSP must have size at least 2^Ω̃(N).
BibTeX  Entry
@InProceedings{cheraghchi_et_al:LIPIcs.STACS.2021.23,
author = {Cheraghchi, Mahdi and Hirahara, Shuichi and Myrisiotis, Dimitrios and Yoshida, Yuichi},
title = {{OneTape Turing Machine and Branching Program Lower Bounds for MCSP}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {23:123:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771801},
ISSN = {18688969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13668},
URN = {urn:nbn:de:0030drops136681},
doi = {10.4230/LIPIcs.STACS.2021.23},
annote = {Keywords: Minimum Circuit Size Problem, Kolmogorov Complexity, OneTape Turing Machines, Branching Programs, Lower Bounds, Pseudorandom Generators, Hitting Set Generators}
}
10.03.2021
Keywords: 

Minimum Circuit Size Problem, Kolmogorov Complexity, OneTape Turing Machines, Branching Programs, Lower Bounds, Pseudorandom Generators, Hitting Set Generators 
Seminar: 

38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Issue date: 

2021 
Date of publication: 

10.03.2021 