2024/05/16 by Alexander Golovnev, Golovnev, Alexander, Zeyu Guo +7
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Neural Networks and Applications
paper · pdf · doi:10.48550/arxiv.2405.10277
openalex publication_date 2024/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For S⊆ \mathbbFn, consider the linear space of restrictions of degree-d polynomials to S. The Hilbert function of S, denoted hS(d,\mathbbF), 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 \mathbbFn 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 \mathbbFqn, 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.