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.