Deterministic restrictions in circuit complexity
Shiva Chaudhuri, Jaikumar Radhakrishnan · 1996
We study the complexity of computing Boolean functions using AND, OR and NOT gates. We show that a circuit of depth d with S gates can be made to output a constant by setting O(S 1−ɛ(d) ) (where ɛ(d) = 4 −d) of its input values. This implies a superlinear size lower bound for a large class of functions. Using this, we obtain a function computable by a uniform family of constant depth polynomial size circuits that cannot be computed by constant depth circuits of linear size. We give circuit constructions that show that the bound O(S 1−ɛ(d) ) is near optimal. We also study the complexity of computing threshold functions. The function T n r has the value 1 iff at least r of its inputs have the value 1. We show that a circuit computing T n r has at least Ω(r 2 (log n) / log r) gates, for r ≤ n 1/3, improving previous bounds. We also show a trade-off between the number of gates and the number of wires in a threshold circuit, namely, a circuit with G (< n/2) gates and W wires computing T n r satisfies W ≥ Ω(nr(log n)/(log(G / log n))), showing that it is not possible to simultaneously optimize the number of gates and wires in a threshold circuit. Our bounds for threshold functions are based on a combinatorial lemma of independent interest. 1