Data Science & Deep Learning: One-tape Turing Machine and Branching Program Lower Bounds for MCSP

Dimitrios Myrisiotis (Computing of Imperial College London)

Wednesday, 10.02.2021, 12:30

Zoom Lecture:
96255595054

For password to lecture, please contact: mayasidis@cs.technion.ac.il

For password to lecture, please contact: mayasidis@cs.technion.ac.il

For a size parameter s: N -> 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 -> {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 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^{\mu_2 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 Neciporuk 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 \tilde{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^{\tilde{\Omega}(N)}.

(To appear STACS 2021).

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 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 Neciporuk 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 \tilde{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^{\tilde{\Omega}(N)}.

(To appear STACS 2021).