Hitting Sets for Low-Degree Polynomials with Optimal Density

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

Popoln opis

Bibliografske podrobnosti
Main Authors: Guruswami, Venkatesan, Xing, Chaoping
Drugi avtorji: School of Physical and Mathematical Sciences
Format: Conference Paper
Jezik:English
Izdano: 2015
Teme:
Online dostop:https://hdl.handle.net/10356/81328
http://hdl.handle.net/10220/39228