Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > CHAO YAN:
All reports by Author Chao Yan:

TR24-092 | 16th May 2024
Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan

Hilbert Functions and Low-Degree Randomness Extractors

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 ... more >>>




ISSN 1433-8092 | Imprint