Hilbert Functions and Low-Degree Randomness Extractors
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910449870569472 |
|---|---|
| author | Golovnev, Alexander Guo, Zeyu Hatami, Pooya Nagargoje, Satyajeet Yan, Chao |
| author_facet | Golovnev, Alexander Guo, Zeyu Hatami, Pooya Nagargoje, Satyajeet Yan, Chao |
| contents | For $S\subseteq \mathbb{F}^n$, consider the linear space of restrictions of degree-$d$ polynomials to $S$. The Hilbert function of $S$, denoted $\mathrm{h}_S(d,\mathbb{F})$, is the dimension of this space. We obtain a tight lower bound on the smallest value of the Hilbert function of subsets $S$ of arbitrary finite grids in $\mathbb{F}^n$ with a fixed size $|S|$. We achieve this by proving that this value coincides with a combinatorial quantity, namely the smallest number of low Hamming weight points in a down-closed set of size $|S|$.
Understanding the smallest values of Hilbert functions is closely related to the study of degree-$d$ closure of sets, a notion introduced by Nie and Wang (Journal of Combinatorial Theory, Series A, 2015). We use bounds on the Hilbert function to obtain a tight bound on the size of degree-$d$ closures of subsets of $\mathbb{F}_q^n$, which answers a question posed by Doron, Ta-Shma, and Tell (Computational Complexity, 2022).
We use the bounds on the Hilbert function and degree-$d$ closure of sets to prove that a random low-degree polynomial is an extractor for samplable randomness sources. Most notably, we prove the existence of low-degree extractors and dispersers for sources generated by constant-degree polynomials and polynomial-size circuits. Until recently, even the existence of arbitrary deterministic extractors for such sources was not known. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_10277 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hilbert Functions and Low-Degree Randomness Extractors Golovnev, Alexander Guo, Zeyu Hatami, Pooya Nagargoje, Satyajeet Yan, Chao Computational Complexity For $S\subseteq \mathbb{F}^n$, consider the linear space of restrictions of degree-$d$ polynomials to $S$. The Hilbert function of $S$, denoted $\mathrm{h}_S(d,\mathbb{F})$, is the dimension of this space. We obtain a tight lower bound on the smallest value of the Hilbert function of subsets $S$ of arbitrary finite grids in $\mathbb{F}^n$ with a fixed size $|S|$. We achieve this by proving that this value coincides with a combinatorial quantity, namely the smallest number of low Hamming weight points in a down-closed set of size $|S|$. Understanding the smallest values of Hilbert functions is closely related to the study of degree-$d$ closure of sets, a notion introduced by Nie and Wang (Journal of Combinatorial Theory, Series A, 2015). We use bounds on the Hilbert function to obtain a tight bound on the size of degree-$d$ closures of subsets of $\mathbb{F}_q^n$, which answers a question posed by Doron, Ta-Shma, and Tell (Computational Complexity, 2022). We use the bounds on the Hilbert function and degree-$d$ closure of sets to prove that a random low-degree polynomial is an extractor for samplable randomness sources. Most notably, we prove the existence of low-degree extractors and dispersers for sources generated by constant-degree polynomials and polynomial-size circuits. Until recently, even the existence of arbitrary deterministic extractors for such sources was not known. |
| title | Hilbert Functions and Low-Degree Randomness Extractors |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2405.10277 |