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 -