דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
Dimitrios Myrisiotis (Computing of Imperial College London)
event date icon
יום רביעי, 10.02.2021, 12:30
event location icon
Zoom Lecture: 96255595054
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).