The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling
Zachary Remscrim · 2016
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 GF(2) of substantially higher degree than the current state-of-the-art construction. We also exactly determine the GF(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 concerning VC dimension, interpolation degree and the Hilbert function.