A Robust Version of Hegedűs's Lemma, with Applications
share
Hegedűs's lemma is the following combinatorial statement regarding polynomials over finite fields. Over a field of characteristic p > 0 and for q a power of p, the lemma says that any multilinear polynomial P∈[x_1,…,x_n] of degree less than q that vanishes at all points in {0,1}^n of Hamming weight k∈ [q,n-q] must also vanish at all points in {0,1}^n of weight k + q. This lemma was used by Hegedűs (2009) to give a solution to Galvin's problem, an extremal problem about set systems; by Alon, Kumar and Volk (2018) to improve the best-known multilinear circuit lower bounds; and by Hrubeš, Ramamoorthy, Rao and Yehudayoff (2019) to prove optimal lower bounds against depth-2 threshold circuits for computing some symmetric functions. In this paper, we formulate a robust version of Hegedűs's lemma. Informally, this version says that if a polynomial of degree o(q) vanishes at most points of weight k, then it vanishes at many points of weight k+q. We prove this lemma and give three different applications.
READ FULL TEXT