Hitting Sets for Low-Degree Polynomials with Optimal Density

• Main Authors: Guruswami, Venkatesan, Xing, Chaoping
• Other Authors: School of Physical and Mathematical Sciences
• Format: Conference or Workshop Item
• Language: English
• Published: 2015
• Subjects: Pseudorandomness; Explicit constructions; ReedMuller codes; Algebraic function fields
• Online Access: https://hdl.handle.net/10356/81328; http://hdl.handle.net/10220/39228
• Institution: Nanyang Technological University

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