Lower bounds for approximations by low degree polynomials over Zm

N. Alon, R. Beigel

Research output: Contribution to journalConference article

25 Scopus citations

Abstract

A Ramsey-theoretic argument is used to obtain the first lower bounds for approximations over Zm by nonlinear polynomials. Nonapproximability results imply the first known lower bounds on the top of MAJ · MODm · AND0(1) circuits that compute parity.

Original languageEnglish (US)
Pages (from-to)184-187
Number of pages4
JournalProceedings of the Annual IEEE Conference on Computational Complexity
StatePublished - Jan 1 2001
Externally publishedYes
Event16th Annual IEEE Conference on Computational Complexity - Chicago, IL, United States
Duration: Jun 18 2001Jun 21 2001

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Lower bounds for approximations by low degree polynomials over Z<sub>m</sub>'. Together they form a unique fingerprint.

  • Cite this