Name
Abstract | ||
|---|---|---|
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 not equal 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/ logN) 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 N1.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 (O) over tilde(root 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((Omega) over tilde (N)). |
Year | DOI | Venue |
|---|---|---|
2021 | 10.4230/LIPIcs.STACS.2021.23 | 38TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2021) |
Keywords | DocType | Volume |
Minimum Circuit Size Problem, Kolmogorov Complexity, One-Tape Turing Machines, Branching Programs, Lower Bounds, Pseudorandom Generators, Hitting Set Generators | Conference | 187 |
ISSN | Citations | PageRank |
1868-8969 | 0 | 0.34 |
References | Authors | |
20 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mahdi Cheraghchi | 1 | 8 | 1.60 |
| Shuichi Hirahara | 2 | 3 | 7.48 |
| Dimitrios Myrisiotis | 3 | 0 | 0.34 |
| Yuichi Yoshida | 4 | 469 | 44.88 |