Small sample spaces cannot fool low degree polynomials

Noga Alon, Ido Ben-Eliezer, Michael Krivelevich

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings
Pages266-275
Number of pages10
DOIs
StatePublished - 2008
Event11th 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 2008Aug 27 2008

Publication series

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

Other

Other11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008
CountryUnited States
CityBoston, MA
Period8/25/088/27/08

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Small sample spaces cannot fool low degree polynomials'. Together they form a unique fingerprint.

Cite this