Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SET SYSTEMS:
Reports tagged with Set Systems:
TR96-004 | 18th January 1996
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-\epsilon(d)})$ (where
$\epsilon(d) = 4^{-d}$) of its input values. This implies a