Title: Lower Bounds for Approximations by Low Degree Polynomials Over Zm

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 Zm by nonlinear polynomials:

These nonapproximability results imply the first known lower bounds on the top fanin of MAJ o MODm o ANDO(1) circuits (i.e., circuits with a single majority-gate at the output node, MODm-gates at the middle level, and constant-fanin AND-gates at the input level) that compute parity: Similar results hold for the MODq function as well.

Download Full Paper