Paper Info
Title
A robust version of Hegedus’s lemma, with applications
Abstract
Hegedűs’s lemma is the following combinatorial statement regarding polynomials over finite fields. Over a field F of characteristic p > 0 and for q a power of p, the lemma says that any multilinear polynomial P∈ F[x1,…,xn] 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 the following three different applications. 1. Degree lower bounds for the coin problem: The δ-Coin Problem is the problem of distinguishing between a coin that is heads with probability ((1/2) + δ) and a coin that is heads with probability 1/2. We show that over a field of positive (fixed) characteristic, any polynomial that solves the δ-coin problem with error ε must have degree Ω(1/δlog(1/ε)), which is tight up to constant factors. 2. Probabilistic degree lower bounds: The Probabilistic degree of a Boolean function is the minimum d such that there is a random polynomial of degree d that agrees with the function at each point with high probability. We give tight lower bounds on the probabilistic degree of every symmetric Boolean function over positive (fixed) characteristic. As far as we know, this was not known even for some very simple functions such as unweighted Exact Threshold functions, and constant error. 3. A robust version of the combinatorial result of Hegedűs (2009) mentioned above.
Year
DOI
Venue
2020
10.1145/3357713.3384328
STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing Chicago IL USA June, 2020
Keywords
DocType
ISSN
Polynomial Method, Polynomial approximations, Symmetric functions, Coin Problem
Conference
0737-8017
ISBN
Citations 
PageRank 
978-1-4503-6979-4
0
0.34
References 
Authors
0
1
Name
Order
Citations
PageRank
Srikanth Srinivasan113221.31