In *Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS)*, 2021. Invited to the special issue of Theory of Computing Systems.

Link Paper doi abstract bibtex

Link Paper doi abstract bibtex

For a size parameter $s:ℕ\toℕ$, 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\}^n \to \{0,1\}$ (represented by a string of length $N := 2^n$) 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 $μ_1 > 0$, if $MCSP[2^{μ_1· 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\neq 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^{μ_2· n}]$ in time $N^{1.99}$, for some constant $μ_2 > μ_1$. 2) A non-deterministic (or parity) branching program of size $o(N^{1.5}/łog 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. 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 $\widetilde{O}(\sqrt{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^{\widetilde{Ω}(N)}$.

@INPROCEEDINGS{ref:conf:CHMY21, author = {Mahdi Cheraghchi and Shuichi Hirahara and Dimitrios Myrisiotis and Yuichi Yoshida}, title = {One-tape Turing machine and branching program lower bounds for {MCSP}}, booktitle = {Proceedings of the 38th {International Symposium on Theoretical Aspects of Computer Science (STACS)}}, year = 2021, keywords = {Minimum Circuit Size Problem, One-Tape Turing Machines, Branching Programs, Lower Bounds, Pseudorandom Generators, Hitting Set Generators}, doi = {10.4230/LIPIcs.STACS.2021.23}, url_Link = {https://drops.dagstuhl.de/opus/volltexte/2021/13668/}, url_Paper = {https://eccc.weizmann.ac.il/report/2020/103/}, note = {Invited to the special issue of Theory of Computing Systems.}, abstract = {For a size parameter $s:\mathbb{N}\to\mathbb{N}$, 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\}^n \to \{0,1\}$ (represented by a string of length $N := 2^n$) 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 $\mu_1 > 0$, if $MCSP[2^{\mu_1\cdot 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\neq 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^{\mu_2\cdot n}]$ in time $N^{1.99}$, for some constant $\mu_2 > \mu_1$. 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\v{c}iporuk method to MKTP, which previously appeared to be difficult. 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 $\widetilde{O}(\sqrt{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^{\widetilde{\Omega}(N)}$. } }

Downloads: 0