## Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An
Easy Witness Lemma for NP and NQP

by Cody Murray and Ryan Williams

#### Oded's comments

I would start from the conclusion,
which is stated in the second paragraph of the abstract.
This work obtains more explicit lower bounds for ACC,
where the demonstrated uniform complexity of functions outside ACC
is reduced from NEXP
(as obatined in Ryan's breakthrough result)
to NQP (nondeterministic quasi-polynomial time).
This is quite an achievement, to say the least...

The foregoing fantastic result is obtained by providing
a generalization of the ``Easy Witness Lemma''
of Impagliazzo, Kabanets, and Wigderson [JCSS'02].
The generalization refers to any set $S$ in NTIME(t),
and provides circuits of size $s(s(s(n)))$
that generate bits of adequate witnesses
(i.e., for each $n$-bit string in $S$
there exists a circuit whose truth-table equals a witness)
whenever the set $S$ can be decided by circuits of
size $s(n/O(1))^{1/O(1)}$.
(IKW proved this result only for exponential $t$;
i.e., $t(n)=\exp(\poly(n))$).
Using the stronger lemma,
one can apply Ryan's method
to NTIME(t) rather than to NEXP.

#### The original abstract

We prove that if every problem in NP has $n^k$-size circuits for a fixed
constant $k$, then for every NP-verifier and every yes-instance $x$ of
length $n$ for that verifier, the verifier's search space has an
$n^{O(k^3)}$-size witness circuit: a witness for $x$ that can be encoded
with a circuit of only $n^{O(k^3)}$ size. An analogous statement is proved
for nondeterministic quasi-polynomial time,
i.e., $NQP = NTIME[n^{\log^{O(1)} n}]$.
This significantly extends the Easy Witness Lemma
of Impagliazzo, Kabanets, and Wigderson [JCSS'02]
which only held for larger nondeterministic classes such as NEXP.

As a consequence, the connections between circuit-analysis algorithms and
circuit lower bounds can be considerably sharpened: algorithms for
approximately counting satisfying assignments to given circuits which
improve over exhaustive search can imply circuit lower bounds for functions
in NQP, or even NP. To illustrate, applying known algorithms for
satisfiability of $ACC \circ THR$ circuits [R. Williams, STOC 2014] we
conclude that for every fixed $k$,
NQP does not have $n^{\log^k n}$-size $ACC \circ THR$ circuits.

See ECCC TR17-188.

Back to
list of Oded's choices.