NDLI: Optimal Testing of Reed-Muller Codes

Content Provider	IEEE Xplore Digital Library
Author	Bhattacharyya, A. Kopparty, S. Schoenebeck, G. Sudan, M. Zuckerman, D.
Copyright Year	2010
Abstract	We consider the problem of testing if a given function $f : \F_2^n \right arrow \F_2$ is close to any degree $d$ polynomial in $n$ variables, also known as the Reed-Muller testing problem. %The Gowers norm is based on a natural $2^{d+1}$-query test for this property. Alon et al.~\cite{AKKLR} proposed and analyzed a natural $2^{d+1}$-query test for this problem. This test turned out to be intimately related to the Gowers norm. Alon et. al. showed that this test accepts every degree $d$ polynomial with probability $1$, while it rejects functions that are $\Omega(1)$-far with probability $\Omega(1/(d 2^{d}))$. We give an asymptotically optimal analysis of this test, and show that it rejects functions that are (even only) $\Omega(2^{-d})$-far with $\Omega(1)$-probability (so the rejection probability is a universal constant independent of $d$ and $n$). This implies a tight relationship between the $(d+1)^{\rm{st}}$-Gowers norm of a function and its maximal correlation with degree $d$ polynomials, when the correlation is close to 1. Our proof works by induction on $n$ and yields a new analysis of even the classical Blum-Luby-Rubinfeld~\cite{BLR} linearity test, for the setting of functions mapping $\F_2^n$ to $\F_2$. The optimality follows from a tighter analysis of counterexamples to the ``inverse conjecture for the Gowers norm'' constructed by \cite{GT07, LMS}. Our result has several implications. First, it shows that the Gowers norm test is tolerant, in that it also accepts close code words. Second, it improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson~\cite{VW}. Third, it implies a ``query hierarchy'' result for property testing of affine-invariant properties. That is, for every function $q(n)$, it gives an affine-invariant property that is testable with $O(q(n))$-queries, but not with $o(q(n))$-queries, complementing an analogous result of \cite{GKNR08} for graph properties.
Starting Page	488
Ending Page	497
File Size	682772
Page Count	10
File Format	PDF
ISBN	9781424485253
ISSN	02725428
DOI	10.1109/FOCS.2010.54
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-10-23
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Polynomials Testing Complexity theory Correlation Computer science Electronic mail Linearity Low-degree tests Sublinear-time algorithms Property testing Reed-Muller codes Gowers norm
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

Optimal Testing of Multivariate Polynomials over Small Prime Fields

Optimal testing of Reed-Muller codes

Optimal testing of Reed–Muller codes

Low-degree tests at large distances (2007)

Hitting Sets for Low-Degree Polynomials with Optimal Density

Optimal testing of Reed-Muller codes (2009)

Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes

Inverse conjecture for the gowers norm is false

Optimal Testing of Reed-Muller Codes

Similar Documents

Optimal Testing of Multivariate Polynomials over Small Prime Fields

Optimal Testing of Multivariate Polynomials over Small Prime Fields

Optimal testing of Reed-Muller codes

Optimal testing of Reed–Muller codes

Low-degree tests at large distances (2007)

Hitting Sets for Low-Degree Polynomials with Optimal Density

Optimal testing of Reed-Muller codes (2009)

Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes

Inverse conjecture for the gowers norm is false

Optimal Testing of Reed-Muller Codes