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

This publication has 11 references indexed in Scilit:

• The monotone circuit complexity of boolean functions
  Combinatorica, 1987
• Threshold functions and bounded depth monotone circuits
  Journal of Computer and System Sciences, 1986
• Almost optimal lower bounds for small depth circuits
  Published by Association for Computing Machinery (ACM) ,1986
• Separating the polynomial-time hierarchy by oracles
  Published by Institute of Electrical and Electronics Engineers (IEEE) ,1985
• Parity, circuits, and the polynomial-time hierarchy
  Theory of Computing Systems, 1984
• On monotone formulae with restricted depth
  Published by Association for Computing Machinery (ACM) ,1984
• A Boolean function requiring 3n network size
  Theoretical Computer Science, 1983
• ∑11-Formulae on finite structures
  Annals of Pure and Applied Logic, 1983
• Exponential lower bounds for restricted monotone circuits
  Published by Association for Computing Machinery (ACM) ,1983
• Parity, circuits, and the polynomial-time hierarchy
  Published by Institute of Electrical and Electronics Engineers (IEEE) ,1981