首页    期刊浏览 2024年11月07日 星期四
登录注册

文章基本信息

  • 标题:The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling
  • 本地全文:下载
  • 作者:Zachary Remscrim ; Zachary Remscrim
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2016
  • 卷号:2016
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要: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 F 2 of substantially higher degree than the current state-of-the-art construction. We also exactly determine the 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.
国家哲学社会科学文献中心版权所有