ECCC-Report TR20-103https://eccc.weizmann.ac.il/report/2020/103Comments and Revisions published for TR20-103en-usWed, 15 Jul 2020 00:17:06 +0300
Revision 1
| One-Tape Turing Machine and Branching Program Lower Bounds for MCSP |
Mahdi Cheraghchi,
Shuichi Hirahara,
Dimitrios Myrisiotis,
Yuichi Yoshida
https://eccc.weizmann.ac.il/report/2020/103#revision1 For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{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 ${\rm 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 ${\rm P}\neq{\rm NP}$.
In this paper, we present the following new lower bounds against one-tape Turing machines and branching programs:
\begin{enumerate}
\item A randomized two-sided error one-tape Turing machine (with an additional one-way read-only input tape) cannot compute ${\rm MCSP}[2^{\mu_2\cdot n}]$ in time $N^{1.99}$, for some constant $\mu_2 > \mu_1$.
\item 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 Nechiporuk method to MKTP, which previously appeared to be difficult.
\end{enumerate}
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:
\begin{enumerate}
\item 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.
\item Any read-once co-non-deterministic branching program computing MCSP must have size at least $2^{\widetilde{\Omega}(N)}$.
\end{enumerate}Wed, 15 Jul 2020 00:17:06 +0300https://eccc.weizmann.ac.il/report/2020/103#revision1
Paper TR20-103
| One-Tape Turing Machine and Branching Program Lower Bounds for MCSP |
Mahdi Cheraghchi,
Shuichi Hirahara,
Dimitrios Myrisiotis,
Yuichi Yoshida
https://eccc.weizmann.ac.il/report/2020/103 For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{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 ${\rm 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 ${\rm P}\neq{\rm NP}$.
In this paper, we present the following new lower bounds against one-tape Turing machines and branching programs:
\begin{enumerate}
\item A randomized two-sided error one-tape Turing machine (with an additional one-way read-only input tape) cannot compute ${\rm MCSP}[2^{\mu_2\cdot n}]$ in time $N^{1.99}$, for some constant $\mu_2 > \mu_1$.
\item 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 Nechiporuk method to MKTP, which previously appeared to be difficult.
\end{enumerate}
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:
\begin{enumerate}
\item 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.
\item Any read-once co-non-deterministic branching program computing MCSP must have size at least $2^{\widetilde{\Omega}(N)}$.
\end{enumerate}Sat, 11 Jul 2020 08:31:21 +0300https://eccc.weizmann.ac.il/report/2020/103