On simple functions, non-determinism, and depth-three circuits

by Les Valiant (1977 and 1983).

Preface

This is a first entry of its type; that is, a review of a very old work or part of it. I will make such entries whenever I encounter an important old idea that I regret not having known before.

The actual post

The underlying technique seems to belong to the bread and butter of circuit complexity (e.g., it appears on page 9 of Jukna's book [J]), but may not be well-known in TOC at large (e.g., I did not know it). I will descibe a definition, a theorem, a lemma, and a few ideas.

DEF: A function is called simple if it can be computed by a Boolean circuit of linear size and logarithmic depth, where the depth refers to bounded fan-in.

THM: Every simple function can be computed by a sub-exponential size depth-three Boolean circuit, when $f$ is call sub-exponential if $f(n)=exp(o(n))$.
Indeed, I advocate calling exponential only functions of the form $f(n)=2^{cn}$, for some fixed $c>0$.

LEM: Given a directed acyclic graph of depth $d$ and $m$ edges, one can remove $rm/\log_2 d$ edges to obtain a digraph of depth $d/2^r$.

The first idea is that the computation of any circuit $C$ can be reduced to a non-deterministic computation of a circuit obtained from $C$ as follows: (1) Remove any edge set $E$ from $C$ possibly obtaining several circuits; (2) Introduce non-deterministic (auxiliary) variables for the cut edges; (3) Take the conjunction of the resulting circuits while imposing that the values on the removed (cut) edges fit the values of the auxiliary variables.

Indeed, this is what we do when we reduce CSAT to SAT, but the foregoing lemma allows to do this at a smaller cost of non-determinism. Specifically, applying the lemma to a simple function while setting $r=O(1)$, we get non-determinism $O(n/\log\log n)$ and new depth of $d/O(1)$ for any O(1)$ we wish to have in the new depth. This means that the circuit is decomposed to a conjuction of small circuits, each of size $2^{d/O(1)} = n^{1/O(1)}$, since $d=O(\log n)$ and the original circuit has bounded fan-in.

The last idea is that non-determinism (of amount $n'$) can be replaced by an unbounded OR of fan-in $2^{n'}$. Thus, the entire computation can be performed by an ordinary (unbounded fan-in) depth-three circuit of size $exp(O(n/\log\log n))$. (Remember to replace the small circuits of size $n^{1/O(1)}$ by CNF formulas of size $exp(n^{1/O(1)})$.)

References

It seems that a self-contained exposition of this proof has first appeared in Viola's survey [V09].

[J] Stasys Jukna. Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics, Vol. 27, Springer, 2012.
[V77] Les Valiant. Graph-theoretic arguments in low-level complexity. Mathematical Foundations of Computer Science, Springer, LNCS, Vol. 53, pages 162--176, 1977.
[V83] Les Valiant. Exponential lower bounds for restricted monotone circuits. In 15th STOC, pages 110--117, 1983.
[V09] Emanuele Viola. On the power of small-depth computation. Foundations and Trends in TCS, Now Publishing, Vol. 5, Nr. 1, pages 1-72, 2009.


Back to list of Oded's choices.