ECCC-Report TR18-199https://eccc.weizmann.ac.il/report/2018/199Comments and Revisions published for TR18-199en-usSun, 25 Nov 2018 08:58:14 +0200
Paper TR18-199
| Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds |
Roei Tell,
Lijie Chen
https://eccc.weizmann.ac.il/report/2018/199The 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)=2^{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$).Sun, 25 Nov 2018 08:58:14 +0200https://eccc.weizmann.ac.il/report/2018/199