Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-103 | 15th July 2020 00:17

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

RSS-Feed




Revision #1
Authors: Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida
Accepted on: 15th July 2020 00:17
Downloads: 147
Keywords: 


Abstract:

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}



Changes to previous version:

Added missing references; fixed typos.


Paper:

TR20-103 | 9th July 2020 01:56

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


Abstract:

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}



ISSN 1433-8092 | Imprint