Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-199 | 24th November 2018 12:35

Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds


Authors: Lijie Chen, Roei Tell
Publication: 25th November 2018 08:58
Downloads: 3409


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)=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$).

ISSN 1433-8092 | Imprint