EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Robust Version of Heged\H{u}s's Lemma, with Applications

Srikanth Srinivasan

TheoretiCS · 2023

DOI: 10.46298/theoretics.23.5 ↗

Kurz gefasst

Fachartikel in der Zeitschrift TheoretiCS, 2023. Verfasst von Srikanth Srinivasan. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Heged\H{u}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\H{u}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\v{s}, 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\H{u}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.

Zitieren

APA

Srinivasan, S. (2023). A Robust Version of Heged\H{u}s's Lemma, with Applications. TheoretiCS. https://doi.org/10.46298/theoretics.23.5

Vancouver

Srinivasan S. A Robust Version of Heged\H{u}s's Lemma, with Applications. TheoretiCS. 2023. doi:10.46298/theoretics.23.5

BibTeX
@article{Srinivasan2023,
  author = {Srinivasan, Srikanth},
  title = {A Robust Version of Heged\Hus's Lemma, with Applications},
  journal = {TheoretiCS},
  year = {2023},
  doi = {10.46298/theoretics.23.5}
}
Kostenlos starten →