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

N. Blum, ?Boolean functions requiring 3n network size,? Theor. Comput. Sci.,28, 337?345 (1984).

M. Furst, J. B. Saxe, and M. Sipser, ?Parity, circuits, and the polynomial time hierarchy,? Proc. 22nd Ann. IEEE Symp. on Foundations of Computer Sci. (1981), pp. 260?270.

M. Furst, J. B. Saxe, and M. Sipser, ?Parity, circuits, and the polynomial time hierarchy,? Math. Syst. Theory,17, 13?27 (1984).

M. Ajtai, ??1 1 formulas on finite structures,? Ann. Pure Appl. Logic,24, 1?48 (1983).

L. G. Valiant, ?Exponential lower bounds for restricted monotone circuits,? Proc. 15th Ann. ACM Symp. on Theory of Comp. (1983), pp. 110?187.

R. Boppana, ?Threshold functions and bounded depth monotone circuits,? Proc. 16th Ann. ACM Symp. on Theory of Comp. (1984), pp. 475?479.

M. Klaw, W. Paul, N. Pippenger, and M. Yannakakis, ?On monotone formulas with restricted depth,? Proc. 16th Ann. ACM Symp. on Theory of Comp. (1984), pp. 475?479.

A. Yao, ?Separating the polynomial-time hierarchy by oracles,? Proc. 26th Ann. IEEE Symp. on Foundations of Computer Science (1985), pp. 1?10.

J. Hastad, ?Almost-optimal lower bounds for small depth circuits,? Preprint (1985).

A. A. Razborov, ?Lower bounds on monotone complexity of some Boolean functions,? Dokl. Akad. Nauk SSSR,281, No. 4, 789?801 (1985).

A. A. Razborov, ?Lower bounds on monotone complexity of a logical permanent,? Mat. Zametki,37, No. 6, 887?900 (1985).

A. E. Andreev, ?On a method of obtaining lower complexity bounds of individual monotone functions,? Dokl. Akad. Nauk SSSR,282, No. 5, 1033?1037 (1985).

N. Alon and R. B. Boppana, ?The monotone circuit complexity of Boolean functions,? Preprint (1985).

D. Yu. Grigor'ev, ?Lower bounds for algebraic complexity of computations,? Computational Complexity Theory, I [in Russian], Zapiski LOMI, Vol. 188, Nauka, Leningrad (1982).

A. A. Razborov, ?Lower bounds on the size of bounded depth circuits over the basis { &, ?, ?},? Usp. Math. Nauk,41, No.4, 219?220 (1986).

R. Smolensky, ?Algebraic methods in the theory of lower bounds for Boolean circuit complexity,? Preprint, Univ. of California, Berkeley (1986).

M. Paterson, ?Bounded depth circuits over {+, ?},? Preprint, Univ. of Warwick (1986).