Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates

This publication has 20 references indexed in Scilit:

• Estimation of certain exponential sums arising in complexity theory
  Comptes Rendus Mathematique, 2005
• Complex polynomials and circuit lower bounds for modular counting
  computational complexity, 1994
• When do extra majority gates help? Polylog (N) majority gates are equivalent to one
  computational complexity, 1994
• On the degree of boolean functions as real polynomials
  computational complexity, 1994
• Hardness vs randomness
  Journal of Computer and System Sciences, 1994
• The expressive power of voting polynomials
  Combinatorica, 1994
• nω(log n) lower bounds on the size of depth-3 threshold cicuits with AND gates at the bottom
  Information Processing Letters, 1993
• On the power of small-depth threshold circuits
  computational complexity, 1991
• Pseudorandom bits for constant depth circuits
  Combinatorica, 1991
• ∑11-Formulae on finite structures
  Annals of Pure and Applied Logic, 1983