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