We knew the best threshold-circuit lower bounds long ago

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?


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