Bootstrapping Results for Threshold Circuits ``Just Beyond''
Known Lower Bounds
by Lijie Chen and Roei Tell
Oded's comments
The message is stated loud and clear in the last paragraph of the abstract,
which refers both to directly obtaining lower bounds (item 1 in the abstract)
and to providing better
quantified derandomizations (item 2),
which in turn yields lower bounds via a reduction of
standard derandomization and Williams's method.
(For prior work of similar flavor, see choice 230.)
The original abstract
The best-known lower bounds for the circuit class $\mathcal{TC}^0$ are only
slightly super-linear. Similarly, the best-known algorithm for
derandomization of this class is an algorithm for quantified
derandomization (i.e., a weak type of derandomization) of circuits of
slightly super-linear size. In this paper we show that even very mild
quantitative improvements of either of the two foregoing results would
already imply super-polynomial lower bounds for $\mathcal{TC}^0$.
Specifically:
- If for every $c>1$ and sufficiently large $d\in\mathbb{N}$ it holds
that $n$-bit $\mathcal{TC}^0$ circuits of depth $d$ require $n^{1+c^{-d}}$
wires to compute certain $\mathcal{NC}^1$-complete functions, then
$\mathcal{TC}^0\ne\mathcal{NC}^1$. In fact, even lower bounds for
$\mathcal{TC}^0$ circuits of size $n^{1+c^{-d}}$ against these functions
when $c>1$ is fixed and sufficiently small would yield lower bounds for
polynomial-sized circuits. Lower bounds of the form $n^{1+c^{-d}}$ against
these functions are already known, but for a fixed $c\approx2.41$ that is
too large to yield new lower bounds via our results.
- If there exists a deterministic algorithm that gets as input an $n$-bit
$\mathcal{TC}^0$ circuit of depth $d$ and $n^{1+(1.61)^{-d}}$ wires, runs
in time $2^{n^{o(1)}}$, and distinguishes circuits that accept at most
$B(n)=3D2^{n^{1-(1.61)^{-d}}}$ inputs from circuits that reject at most
$B(n)$ inputs, then $\mathcal{NEXP}\not\subseteq\mathcal{TC}^0$. An
algorithm for this ``quantified derandomization'' task is already
known, but it works only when the number of wires is $n^{1+c^{-d}}$, for
$c>30$, and with a smaller $B(n)\approx2^{n^{1-(30/c)^{d}}}$.
Intuitively, the ``takeaway'' message from our work is that the gap
between currently-known results and results that would suffice to get
super-polynomial lower bounds for $\mathcal{TC}^0$ boils down to the
precise constant $c>1$ in the bound $n^{1+c^{-d}}$ on the number of
wires. Our results improve previous results of Allender and Kouck\'y
(2010) and of the second author (2018), respectively, whose hypotheses
referred to circuits with $n^{1+c/d}$ wires (rather than $n^{1+c^{-d}}$
wires). We also prove results similar to two results above for other
circuit classes (i.e., $\mathcal{ACC}^0$ and $\mathcal{CC}^0$).
See ECCC TR18-199.
Back to
list of Oded's choices.