Srikanth Srinivasan - A Robust Version of Hegedűs's Lemma, with Applications

theoretics:9143 - TheoretiCS, March 1, 2023, Volume 2 -
A Robust Version of Hegedűs's Lemma, with ApplicationsArticle

Authors: Srikanth Srinivasan

    Hegedűs's lemma is the following combinatorial statement regarding polynomials over finite fields. Over a field $\mathbb{F}$ of characteristic $p > 0$ and for $q$ a power of $p$, the lemma says that any multilinear polynomial $P\in \mathbb{F}[x_1,\ldots,x_n]$ of degree less than $q$ that vanishes at all points in $\{0,1\}^n$ of some fixed Hamming weight $k\in [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 \emph{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.

    Volume: Volume 2
    Published on: March 1, 2023
    Accepted on: December 20, 2022
    Submitted on: February 28, 2022
    Keywords: Computer Science - Computational Complexity

    Consultation statistics

    This page has been seen 488 times.
    This article's PDF has been downloaded 135 times.