We study the following question: Is it easier to construct a hitting-set generator for polynomials p : F n F of degree d if we are guaranteed that the polynomial vanishes on at most an 0"> 0 fraction of its inputs? We will specifically be interested in tiny values of d F . This question was first asked by Goldreich and Wigderson (STOC 2014), who studied a specific setting geared for an application, and another specific setting was later studied by the third author (CCC 2017).

In this work our main interest is a *systematic study of the problem itself*, in its general form, and we prove results that significantly extend and improve the two previously-known results. Our contributions are of two types:

1. Over fields of size 2 F p ol y ( n ) , we show that the seed length of any hitting-set generator for polynomials of degree d n 49 that vanish on at most = F − t of their inputs is at least ( d t ) log ( n ) .2. Over F 2 , we show that there exists a (non-explicit) hitting-set generator for polynomials of degree d n 99 that vanish on at most = F − t of their inputs with seed length O ( d − t ) log ( n ) . We also show a polynomial-time computable hitting-set generator with seed length O ( d − t ) 2 d − t + log ( n ) .In addition, we prove that the problem we study is closely related to the following question: ``Does there exist a small set S F n whose degree- d closure is very large?'', where the degree- d closure of S is the variety induced by the set of degree- d polynomials that vanish on S . We then use our lower bounds on hitting-sets for polynomials that vanish rarely to deduce lower bounds for this question.