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?

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.

A dream come true, sort of: E-ink monitors

Spending your life staring at a (traditional) computer screen may not be ideal for your eyes (and more); so since an early age I have been dreaming of a “purely mechanical” monitor that you could stare at more or less indefinitely, like at parchment.

This dream is now becoming reality, sort of.  The Dasung E-ink monitor has no backlight and instead reportedly uses electric flows to move ink droplets.

After some consideration, spending yet more hours reading reviews online and watching youtube videos about it sealed the deal.  I shelled out $1300 and bought the thing.

I have had it for a few days now and I am sort of happy. I went from using a giant 30-inch monitor far away (my theory for avoiding eye strain) to using a ~13-inch monitor at pretty much the same distance as reading a book. I had to avoid sunlight, now I seek it (see the picture).

20190307_094550

The monitor makes your computer look like Windows 3.1 on a monochrome screen from the 80’s. The refresh is slow, and there is a ghosting effect, meaning there are shadows of previous images — which you can clear out. Also, it’s 4:3 instead of 16:9, which is a pain because it means I have to change resolution when I am forced to use my other monitor (for example if I have to check colors — the screen is gray-scale, did I mention that?). It makes browsing the internet quite painful, which is a nice side effect.

Contrary to advice, I am using it as my primary monitor. I am sort of happy with it and don’t regret buying it. I have started writing and reading papers with it and it’s working well enough.

I think as soon as the technology improves the market for these things will be huge.  Already having a 17″ monitor in 16:9 ratio, ideally touch-screen, even if gray scale, would be a dream come true.