We knew the best threshold-circuit lower bounds long ago

Thoughts 2019-08-20

For more than 20 years we’ve had $n^{1+c^{-d}}$ lower bounds for threshold circuits of depth $d$ [IPS97], for a fixed $c$ . There have been several “explanations” for the lack of progress [AK10]. Recently Chen and Tell have given a better explanation showing that you can’t even improve the result to a better $c$ without proving “the whole thing.”

Say you have a finite group $G$ and you want to compute the iterated product of $n$ elements.

Warm-up [AK10]..

Suppose you can compute this with circuits of size $s(n)=n^{10}$ and depth $10$ . Now we show how you can trade size for depth. Put a complete tree with fan-in $f$ on top of the group product, where each node computes the product of its children (this is correct by associativity, in general this works for a monoid). This tree needs depth $\log _{f}n$ . If you stick your circuit of size $s(n)$ and depth $O(1)$ at each node, the depth of the overall circuit would be obviously $O(\log _{f}n)$ and the overall size would be dominated by the input layer which is $s(f)\cdot n/f<s(f)\cdot n$ . If you are aiming for overall depth $d$ , you need $f=n^{O(1/d)}$ . This gives size $n^{1+O(1/d)}$ .

Hence we have shown that proving bounds $n^{1+\omega (1/d)}$ for some depth $d$ suffices to prove $n^{10}$ lower bounds for depth $10$ .

Chen and Tell..

The above is not the most efficient way to build a tree! I am writing this post following their paper to understand what they do. As they say, the idea is quite simple. While above the size will be dominated by the input layer, we want to balance things so that every layer has roughly the same contribution.

Let’s say we are aiming for size $n^{1+\epsilon }$ and let’s see what depth we can get. Let’s say now the size is $s(n)=n^{k}$ . Let us denote by $n_{i}$ the number of nodes at level $i$ with $i=0$ being the root. The fan-in at level $i$ is $(n^{1+\epsilon }/n_{i})^{1/k}$ so that the cost is $n^{1+\epsilon }$ as desired. We have the recursion $n_{i+1}=n_{i}\cdot (n^{1+\epsilon }/n_{i})^{1/k}$ .

The solution to this recursion is $n_{i}=n^{(1+\epsilon )(1-(1-1/k)^{i})}$ , see below.

So that’s it. We need to get to $n$ nodes. So if you set $i=O(k\log (1/\epsilon ))$ you get say $n_{i}=n^{(1+\epsilon )(1-\epsilon ^{2})}>n$ . Going back to $k=10$ , we have exhibited circuits of size $n^{1+\epsilon }$ and depth just $O(\log 1/\epsilon )$ . So proving stronger bounds than this would rule out circuits of size $n^{10}$ and depth $10$ .

Added later: About the recurrence.

Letting $a_{i}:=\log _{n}n_{i}$ we have the following recurrence for the exponents of $n_{i}$ .

$\begin{aligned} a_{0} & =0\\ a_{i+1} & =a_{i}(1-1/k)+(1+\epsilon )/k=:a_{i}b+c. \end{aligned}$

This gives

$\begin{aligned} a_{i}=c\sum _{j\le i}b{}^{j}=c\frac {1-b^{i+1}}{1-b}=(1+\epsilon )(1-b^{i+1}). \end{aligned}$

If it was $a'_{i+1}=a'_{i}+(1+\epsilon )/k$ obviously $a'_{k}$ would already be $1+\epsilon$ . Instead for $a_{i}$ we need to get to $k\log (1/\epsilon )$ .

My two cents..

I am not sure I need more evidence that making progress on long-standing bounds in complexity theory is hard, but I do find it interesting to prove these links; we have quite a few by now! The fact that we have been stuck forever just short of proving “the whole thing” makes me think that these long-sought bounds may in fact be false. Would love to be proved wrong, but it’s 2019, this connection is proved by balancing a tree better, and you feel confident that P $\ne$ NP?

References

[AK10] Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. of the ACM, 57(3), 2010.

[IPS97] Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks. Size-depth tradeoffs for threshold circuits. SIAM J. Comput., 26(3):693–707, 1997.