Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/81328
Title: Hitting Sets for Low-Degree Polynomials with Optimal Density
Authors: Guruswami, Venkatesan
Xing, Chaoping
Keywords: Pseudorandomness
Explicit constructions
ReedMuller codes
Algebraic function fields
Issue Date: 2014
Source: Guruswami, V., & Xing, C. (2014). Hitting Sets for Low-Degree Polynomials with Optimal Density. 2014 IEEE 29th Conference on Computational Complexity (CCC), 161-168.
Abstract: 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 vanishes on at most delta N points in S. Equivalently, we give an explicit hitting set generator (HSG) for degree-d polynomials of seed length log N = O(d log n + log (1/δ)) with "density" 1-δ (meaning every nonzero polynomial is nonzero with probability at least 1-δ on the output of the HSG). The seed length is optimal up to constant factors, as is the required field size Omega(d/delta). Plugging our HSG into a construction of Bogdanov (STOC'05) gives explicit pseudorandom generators for n-variate degree-d polynomials with error eps and seed length O(d4 log n + log (1/ε)) whenever the field size satisfies q gtrsim d6/ε2. Our approach involves concatenating previously known HSGs over large fields with multiplication friendly codes based on algebraic curves. This allows us to bring down the field size to the optimal bounds. Such multiplication friendly codes, which were first introduced to study the bilinear complexity of multiplication in extension fields, have since found other applications, and in this work we give a further use of this notion in algebraic pseudorandomness.
URI: https://hdl.handle.net/10356/81328
http://hdl.handle.net/10220/39228
DOI: 10.1109/CCC.2014.24
Rights: © 2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: [http://dx.doi.org/10.1109/CCC.2014.24].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Conference Papers

Files in This Item:
File Description SizeFormat 
punctured-RM-dense-hsg.pdf310.51 kBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 20

2
checked on Sep 5, 2020

WEB OF SCIENCETM
Citations 20

2
checked on Sep 24, 2020

Page view(s) 20

281
checked on Sep 30, 2020

Download(s) 20

88
checked on Sep 30, 2020

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.