Lower bounds on the size of bounded depth circuits over a complete basis with logical addition (Q1095871)

Lower bounds for bounded depth circuits over \(\{\) \&,\(\vee,\oplus \}\) are given using a special structure of families of Boolean functions called regular models. The construction of bounded degree is described. These models are then used to deduce exponential lower bounds in the basis \(\{\) \&,\(\oplus \}\), and it is shown that they also hold in the basis \(\{\) \&,\(\vee,\oplus \}\).