Small sample spaces cannot fool low degree polynomials

Noga Alon; Ido Ben-Eliezer; Michael Krivelevich

doi:10.1007/978-3-540-85363-3_22

Small sample spaces cannot fool low degree polynomials

Noga Alon, Ido Ben-Eliezer, Michael Krivelevich

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Scopus citations

Abstract

A distribution D on a set S ⊂ ℤ_p^N ε-fools polynomials of degree at most d in N variables over ℤ_p if for any such polynomial P, the distribution of P(x) when x is chosen according to D differs from the distribution when x is chosen uniformly by at most ε in the ℓ₁ norm. Distributions of this type generalize the notion of ε-biased spaces and have been studied in several recent papers. We establish tight bounds on the minimum possible size of the support S of such a distribution, showing that any such S satisfies |S| ≥ c₁ · ((N/2d^d)· log p/ε² log (1/ε) + p )· This is nearly optimal as there is such an S of size at most c₂· (3N/d)^d· log p + p/ε².

Original language	English (US)
Title of host publication	Approximation, Randomization and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings
Pages	266-275
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-540-85363-3_22
State	Published - 2008
Externally published	Yes
Event	11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008 - Boston, MA, United States Duration: Aug 25 2008 → Aug 27 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5171 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008
Country/Territory	United States
City	Boston, MA
Period	8/25/08 → 8/27/08

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-85363-3_22

Cite this

Alon, N., Ben-Eliezer, I., & Krivelevich, M. (2008). Small sample spaces cannot fool low degree polynomials. In Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings (pp. 266-275). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5171 LNCS). https://doi.org/10.1007/978-3-540-85363-3_22

Alon, Noga ; Ben-Eliezer, Ido ; Krivelevich, Michael. / Small sample spaces cannot fool low degree polynomials. Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. 2008. pp. 266-275 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b8f71265ccc24736be09c6d3a11a501f,

title = "Small sample spaces cannot fool low degree polynomials",

abstract = "A distribution D on a set S ⊂ ℤpN ε-fools polynomials of degree at most d in N variables over ℤp if for any such polynomial P, the distribution of P(x) when x is chosen according to D differs from the distribution when x is chosen uniformly by at most ε in the ℓ1 norm. Distributions of this type generalize the notion of ε-biased spaces and have been studied in several recent papers. We establish tight bounds on the minimum possible size of the support S of such a distribution, showing that any such S satisfies |S| ≥ c1 · ((N/2dd)· log p/ε2 log (1/ε) + p )· This is nearly optimal as there is such an S of size at most c2· (3N/d)d· log p + p/ε2.",

author = "Noga Alon and Ido Ben-Eliezer and Michael Krivelevich",

year = "2008",

doi = "10.1007/978-3-540-85363-3_22",

language = "English (US)",

isbn = "3540853626",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "266--275",

booktitle = "Approximation, Randomization and Combinatorial Optimization",

note = "11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008 ; Conference date: 25-08-2008 Through 27-08-2008",

}

Alon, N, Ben-Eliezer, I & Krivelevich, M 2008, Small sample spaces cannot fool low degree polynomials. in Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5171 LNCS, pp. 266-275, 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008, Boston, MA, United States, 8/25/08. https://doi.org/10.1007/978-3-540-85363-3_22

Small sample spaces cannot fool low degree polynomials. / Alon, Noga; Ben-Eliezer, Ido; Krivelevich, Michael.
Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. 2008. p. 266-275 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5171 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Small sample spaces cannot fool low degree polynomials

AU - Alon, Noga

AU - Ben-Eliezer, Ido

AU - Krivelevich, Michael

PY - 2008

Y1 - 2008

N2 - A distribution D on a set S ⊂ ℤpN ε-fools polynomials of degree at most d in N variables over ℤp if for any such polynomial P, the distribution of P(x) when x is chosen according to D differs from the distribution when x is chosen uniformly by at most ε in the ℓ1 norm. Distributions of this type generalize the notion of ε-biased spaces and have been studied in several recent papers. We establish tight bounds on the minimum possible size of the support S of such a distribution, showing that any such S satisfies |S| ≥ c1 · ((N/2dd)· log p/ε2 log (1/ε) + p )· This is nearly optimal as there is such an S of size at most c2· (3N/d)d· log p + p/ε2.

AB - A distribution D on a set S ⊂ ℤpN ε-fools polynomials of degree at most d in N variables over ℤp if for any such polynomial P, the distribution of P(x) when x is chosen according to D differs from the distribution when x is chosen uniformly by at most ε in the ℓ1 norm. Distributions of this type generalize the notion of ε-biased spaces and have been studied in several recent papers. We establish tight bounds on the minimum possible size of the support S of such a distribution, showing that any such S satisfies |S| ≥ c1 · ((N/2dd)· log p/ε2 log (1/ε) + p )· This is nearly optimal as there is such an S of size at most c2· (3N/d)d· log p + p/ε2.

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

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

U2 - 10.1007/978-3-540-85363-3_22

DO - 10.1007/978-3-540-85363-3_22

M3 - Conference contribution

AN - SCOPUS:51849102459

SN - 3540853626

SN - 9783540853626

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 266

EP - 275

BT - Approximation, Randomization and Combinatorial Optimization

T2 - 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008

Y2 - 25 August 2008 through 27 August 2008

ER -

Alon N, Ben-Eliezer I, Krivelevich M. Small sample spaces cannot fool low degree polynomials. In Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. 2008. p. 266-275. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-85363-3_22

Small sample spaces cannot fool low degree polynomials

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this