This fantastic work provides a crystal clear and highly appealing illustration of the paradigm of obtaining circuit lower bounds via the design of (better) algorithms. For me, this was the high point of the conference, and attending Dylan's talk compensated me for the hardships of being subjected to FCRC and to the weather. (see preamble to Choice 269).
The result chosen for the presentation is based on a super efficient streaming algorithm for MCSP (minimum circuit size problem). The foregoing one-size algorithm uses polylogarithmic space and polylogarithmic update time, and is given access to an oracle in PH. Hence, lower bounds on standards streaming algorithms (which have no oracles) imply that PH is different from P (and so NP is different from P), since PH=P allows to convert this oracle-aided algorithm into a standard one. Note that the streaming lower bound that is needed for the conclusion is very weak, since MCSP is widely believed not to be in P, let alone not be solvable in nearly-linear time, let alone under the foregoing access limitation and space bound.
The oracle-aided streaming algorithm reads a truth-table of a function and maintains a circuit that `explains' (or rather agrees with) a prefix of this function read so far, whereas the update operation is clearly in PH (i.e., we have to find a circuit that agrees with the current circuit on the current prefix length as well as fits the next bit being read).
Of course, one may say that this is merely a reduction (albeit one between problems in different computational models), but the same can be said about the entire paradigm of obtaining circuit lower bounds by the design of algorithms. On the other hand, one can say that any reduction is an algorithm (and so we have been using the algorithmic design paradigm from the early 1970s). But extreme generalization are often less useful than more specific abstractions; that is, restricting the scope may make a method more useful (and indeed any method is a restriction of the set of all possible approaches that could have been taken).
The Minimum Circuit Size Problem (MCSP) asks to determine the minimum size of a circuit computing a given truth table. MCSP is a natural and powerful string compression problem whose NP-hardness remains open. Recently, Oliveira and Santhanam [FOCS2018] and Oliveira, Pich, and Santhanam [ECCC 2018] demonstrated a “hardness magnification” phenomenon for MCSP in re-stricted settings. Letting MCSP[s(n)] be the problem of deciding if a truth table of length $2^n$ has circuit complexity at most s(n), they proved that small (fixed-polynomial) average-case circuit/formula lower bounds for MCSP[$2^{sqrt(n)}$], or lower bounds for approximating MCSP[$2^{o(n)}$], would imply major separations such as NP not in BPP and NP not in P/poly.
We strengthen these results in several directions, obtaining magnification results from worst-case lower bounds on exactly computing the search version of generalizations of MCSP[s(n)], which also extend to time-bounded Kolmogorov complexity. In particular, we show that search-MCSP[s(n)] (where we must output a s(n)-size circuit when it exists) admits extremely efficient AC0 circuits and streaming algorithms using Sigma3-SAT oracle gates of small fan-in (related to the sizes(n) we want to test).
For $A:{0,1}^n\to {0,1}$, let search-MCSP^A[s(n)] be the problem: Given a truth table T of size $N=2^n$, output a Boolean circuit for T of size at most s(n) with AND, OR, NOT, and A-oracle gates (or report that no such circuit exists). Some consequences of our results are:
See STOC'19 program (Session 9B).