Events

# The Taub Faculty of Computer Science Events and Talks

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 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.