NDLI: Hitting Sets for Low-Degree Polynomials with Optimal Density

Content Provider	IEEE Xplore Digital Library
Author	Guruswami, V. Chaoping Xing
Copyright Year	2014
Description	Author affiliation: Sch. of Phys. & Math. Sci., Nanyang Technol. Univ., Singapore, Singapore (Chaoping Xing) \|\| Comput. Sci. Dept., Carnegie Mellon Univ., Pittsburgh, PA, USA (Guruswami, V.)
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 $F_{q}$ with q ≳ d/δ, we present an explicit (multi)-set S ⊆ $F_{q}^{n}$ of size $N=poly(n^{d}/δ)$ 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(d^{4}$ log n + log (1/ε)) whenever the field size satisfies q gtrsim $d^{6}/ε^{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.
Starting Page	161
Ending Page	168
File Size	263357
Page Count	8
File Format	PDF
ISBN	9781479936267
ISSN	10930159
DOI	10.1109/CCC.2014.24
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-06-11
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Polynomials Generators Vectors Linear codes Frequency modulation Complexity theory Algebraic function fields Pseudorandomness Explicit constructions Reed-Muller codes
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Optimal Testing of Multivariate Polynomials over Small Prime Fields

Hitting Set Generators for Sparse Polynomials over Any Finite Fields

Optimal Testing of Reed-Muller Codes

Information sets of Multiplicity codes

Explicit Subspace Designs

Matching Vector Codes

Soft-decision list decoding of Reed-Muller codes with linear complexity

Multiplicative secret sharing schemes from Reed-Muller type codes

Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate

Hitting Sets for Low-Degree Polynomials with Optimal Density

Similar Documents

Optimal Testing of Multivariate Polynomials over Small Prime Fields

Hitting Set Generators for Sparse Polynomials over Any Finite Fields

Optimal Testing of Reed-Muller Codes

Information sets of Multiplicity codes

Explicit Subspace Designs

Matching Vector Codes

Soft-decision list decoding of Reed-Muller codes with linear complexity

Multiplicative secret sharing schemes from Reed-Muller type codes

Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate

Hitting Sets for Low-Degree Polynomials with Optimal Density