Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HITTING-SET GENERATOR:
Reports tagged with Hitting-Set Generator:
TR19-119 | 9th September 2019
Dean Doron, Amnon Ta-Shma, Roei Tell

#### On Hitting-Set Generators for Polynomials that Vanish Rarely

Revisions: 1

We study the following question: Is it easier to construct a hitting-set generator for polynomials $p:\mathbb{F}^n\rightarrow\mathbb{F}$ of degree $d$ if we are guaranteed that the polynomial vanishes on at most an $\epsilon>0$ fraction of its inputs? We will specifically be interested in tiny values of $\epsilon\ll d/|\mathbb{F}|$. This question was ... more >>>

ISSN 1433-8092 | Imprint