Lower bounds for approximations by low degree polynomials over Zm

N. Alon; R. Beigel

Lower bounds for approximations by low degree polynomials over Z_m

N. Alon, R. Beigel

Research output: Contribution to journal › Conference article › peer-review

Abstract

A Ramsey-theoretic argument is used to obtain the first lower bounds for approximations over Z_m by nonlinear polynomials. Nonapproximability results imply the first known lower bounds on the top of MAJ · MOD_m · AND₀₍₁₎ circuits that compute parity.

Original language	English (US)
Pages (from-to)	184-187
Number of pages	4
Journal	Proceedings of the Annual IEEE Conference on Computational Complexity
State	Published - 2001
Externally published	Yes
Event	16th Annual IEEE Conference on Computational Complexity - Chicago, IL, United States Duration: Jun 18 2001 → Jun 21 2001

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Computational Mathematics

Cite this

@article{b96ae86b430a45209c3cef86ea2340ba,

title = "Lower bounds for approximations by low degree polynomials over Zm",

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.",

author = "N. Alon and R. Beigel",

year = "2001",

language = "English (US)",

pages = "184--187",

journal = "Proceedings of the Annual IEEE Conference on Computational Complexity",

issn = "1093-0159",

publisher = "IEEE Computer Society",

note = "16th Annual IEEE Conference on Computational Complexity ; Conference date: 18-06-2001 Through 21-06-2001",

}

TY - JOUR

T1 - Lower bounds for approximations by low degree polynomials over Zm

AU - Alon, N.

AU - Beigel, R.

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0034874724&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034874724&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0034874724

SN - 1093-0159

SP - 184

EP - 187

JO - Proceedings of the Annual IEEE Conference on Computational Complexity

JF - Proceedings of the Annual IEEE Conference on Computational Complexity

T2 - 16th Annual IEEE Conference on Computational Complexity

Y2 - 18 June 2001 through 21 June 2001

ER -

Lower bounds for approximations by low degree polynomials over Z_m

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this