Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-122 | 31st October 2005 00:00

A nonlinear bound on the number of wires in bounded depth circuits

RSS-Feed




TR05-122
Authors: Pavel Pudlak
Publication: 1st November 2005 11:58
Downloads: 1800
Keywords: 


Abstract:

We shall prove a lower bound on the number of edges in some bounded
depth graphs. This theorem is stronger than lower bounds proved on
bounded depth superconcentrators and enables us to prove a lower bound
on certain bounded depth circuits for which we cannot use
superconcentrators: we prove that conjunction cannot be computed by
bounded depth circuits with modular gates that have linear number of
wires.



ISSN 1433-8092 | Imprint