TY - GEN

T1 - Small sample spaces cannot fool low degree polynomials

AU - Alon, Noga

AU - Ben-Eliezer, Ido

AU - Krivelevich, Michael

N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

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 -