Hitting Sets for Low-Degree Polynomials with Optimal Density

• Main Authors: Guruswami, Venkatesan, Xing, Chaoping
• 其他作者: School of Physical and Mathematical Sciences
• 格式: Conference or Workshop Item
• 語言: English
• 出版: 2015
• 主題: Pseudorandomness; Explicit constructions; ReedMuller codes; Algebraic function fields
• 在線閱讀: https://hdl.handle.net/10356/81328; http://hdl.handle.net/10220/39228

We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding n-variate degree-d polynomials over Fq with q ≳ d/δ, we present an explicit (multi)-set S ⊆ Fqn of size N=poly(nd/δ) such that every nonzero polynomial vani...