The Complexity of Finite Functions

This publication has 49 references indexed in Scilit:

• Short monotone formulae for the majority function
  Published by Elsevier ,2004
• Bounded-width polynomial-size branching programs recognize exactly those languages in NC1
  Journal of Computer and System Sciences, 1989
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
  Mathematical Notes, 1987
• Lower bounds on monotone complexity of the logical permanent
  Mathematical Notes, 1985
• Parity, circuits, and the polynomial-time hierarchy
  Theory of Computing Systems, 1984
• A Boolean function requiring 3n network size
  Theoretical Computer Science, 1983
• On the complexity of the marriage problem
  Advances in Mathematics, 1972
• The complexity of the realization of symmetrical functions by formulae
  Mathematical Notes, 1972
• Method of determining lower bounds for the complexity of P-schemes
  Mathematical Notes, 1971
• On the computational complexity of algorithms
  Transactions of the American Mathematical Society, 1965