论文标题
Hegeds的引理的强大版本，并带有应用
A Robust Version of Hegedűs's Lemma, with Applications
论文作者
论文摘要
Hegeds的引理是有关有限领域多项式的以下组合陈述。在字段上$ \ mathbb {f} $的特征$ p> 0 $，对于$ p $ $ p $的$ q $，Lemma说，任何多连线多项式$ p \ in \ mathbb {f} [x_1，\ ldots，x_n] $ best $ q $的$ q $ nielide的$ q $ niment $ q $} $ k \ in [q，n-q] $也必须在$ \ {0,1 \}^n $中的所有点上消失，重量$ k + q $。 HegedűS（2009）使用了这种引理，为\ Emph {Galvin的问题}提供了解决方案，这是SET系统的一个极端问题；作者：Alon，Kumar and Volk（2018），以改善最著名的多线性电路下限；由Hrubeš，Ramamoorthy，Rao和Yehudayoff（2019）证明了最佳的下限，用于计算某些对称功能的深度 - $ 2 $阈值电路。 在本文中，我们制定了Hegeds的引理的强大版本。从非正式的情况下，此版本说，如果大多数重量$ k $的多项式$ o（q）$消失，那么它会在重量$ k+q $的许多重点下消失。我们证明了这种引理并提供了三种不同的应用。
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.
