E-viri
Odprti dostop
-
Golovnev, Alexander; Guo, Zeyu; Hatami, Pooya; Nagargoje, Satyajeet; Chao, Yan
arXiv (Cornell University), 05/2024Paper, Journal Article
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.
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.