Hitting Sets for Low-Degree Polynomials with Optimal Density

• المؤلفون الرئيسيون: 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
• المؤسسة: 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...