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:

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