Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-020 | 8th February 2016 15:23

The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling

RSS-Feed




TR16-020
Authors: Zachary Remscrim
Publication: 19th February 2016 08:44
Downloads: 841
Keywords: 


Abstract:

In this paper, we apply tools from algebraic geometry to prove new results concerning extractors for algebraic sets, the recursive Fourier sampling problem, and VC dimension. We present a new construction of an extractor which works for algebraic sets defined by polynomials over $\mathbb{F}_2$ of substantially higher degree than the current state-of-the-art construction. We also exactly determine the $\mathbb{F}_2$-polynomial degree of the recursive Fourier sampling problem and use this to provide new partial results towards a circuit lower bound for this problem. Finally, we answer a question posed in \cite{moran} concerning VC dimension, interpolation degree and the Hilbert function.



ISSN 1433-8092 | Imprint