to be presented at the 16th Annual *Conference on Computational Complexity*, 2001

**Authors:**
Noga Alon and Richard Beigel

**Abstract:**
We use a Ramsey-theoretic argument to obtain the first lower bounds
for approximations over Z_{m} by nonlinear polynomials:

- A degree-2 polynomial over Z
_{m}(*m*odd) must differ from the parity function on at least a1/2-1/2 fraction of all points in the Boolean^{(logn)Ω(1)}*n*-cube. - A degree-O(1) polynomial over Z
_{m}(*m*odd) must differ from the parity function on at least a1/2-o(1) fraction of all points in the Boolean*n*-cube.

- MAJ o MOD
_{m}o AND_{2}circuits that compute parity must have top fanin 2^{(logn)Ω(1)}. - Parity cannot be computed by
MAJ o MOD _{m}of AND_{O(1)}circuits with top fanin O(1).