Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SET SYSTEMS:
Reports tagged with Set Systems:
TR96-004 | 18th January 1996
Shiva Chaudhuri, Jaikumar Radhakrishnan

Deterministic Restrictions in Circuit Complexity

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-\epsilon(d)})$ (where
$\epsilon(d) = 4^{-d}$) of its input values. This implies a
superlinear size lower bound ... more >>>




ISSN 1433-8092 | Imprint