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:
- A degree-2 polynomial over Zm (m odd) must differ
from the parity function on at least a
1/2-1/2(logn)Ω(1) fraction
of all points in the Boolean n-cube.
- A degree-O(1) polynomial over Zm (m odd) must
differ from the parity function on at least a 1/2-o(1) fraction of
all points in the Boolean n-cube.
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:
- MAJ o MODm o AND2 circuits that compute parity must have
top fanin 2(logn)Ω(1).
- Parity cannot be computed by MAJ o MODm of ANDO(1) circuits with top fanin O(1).
Similar results hold for the MODq function as well.
Download Full Paper