2026-07-25T05:46:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21034 2024-09-16T06:02:39Z ddc:004 open_access

Hilbert Functions and Low-Degree Randomness Extractors Golovnev, Alexander Guo, Zeyu Hatami, Pooya Nagargoje, Satyajeet Yan, Chao Extractors Dispersers Circuits Hilbert Function Randomness Low Degree Polynomials For S ⊆ 𝔽ⁿ, consider the linear space of restrictions of degree-d polynomials to S. The Hilbert function of S, denoted h_S(d,𝔽), 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 𝔽ⁿ 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 𝔽_qⁿ, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Golovnev and Zeyu Guo and Pooya Hatami and Satyajeet Nagargoje and Chao Yan 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.41 urn:nbn:de:0030-drops-210345 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.41 eng https://creativecommons.org/licenses/by/4.0/legalcode