NDLI: Improved Low-Degree Testing and its Applications

Please wait, while we are loading the content...

Improved Low-Degree Testing and its Applications

Content Provider	Springer Nature Link
Author	Arora, Sanjeev Sudan, Madhu
Copyright Year	2003
Abstract	NP = PCP(log n, 1) and related results crucially depend upon the close connection between the probability with which a function passes a low degree test and the distance of this function to the nearest degree d polynomial. In this paper we study a test proposed by Rubinfeld and Sudan [30]. The strongest previously known connection for this test states that a function passes the test with probability δ for some δ > 7/8 iff the function has agreement ≈ δ with a polynomial of degree d. We present a new, and surprisingly strong, analysis which shows that the preceding statement is true for arbitrarily small ≈, provided the field size is polynomially larger than d/δ. The analysis uses a version of Hilbert irreducibility, a tool of algebraic geometry.As a consequence we obtain an alternate construction for the following proof system: A constant prover 1-round proof system for NP languages in which the verifier uses O(log n) random bits, receives answers of size O(log n) bits, and has an error probability of at most $$ 2^{{ - \log ^{{1 - \in }} n}} $$ . Such a proof system, which implies the NP-hardness of approximating Set Cover to within Ω(log n) factors, has already been obtained by Raz and Safra [29]. Raz and Safra obtain their result by giving a strong analysis, in the sense described above, of a new low-degree test that they present.A second consequence of our analysis is a self tester/corrector for any buggy program that (supposedly) computes a polynomial over a finite field. If the program is correct only on δ fraction of inputs where $$ \delta = 1/{\left\| F \right\|}^{ \in } \ll 0.5 $$ , then the tester/corrector determines δ and generates $$ O{\left( {\frac{1} {\delta }} \right)} $$ values for every input, such that one of them is the correct output. In fact, our results yield something stronger: Given the buggy program, we can construct $$ O{\left( {\frac{1} {\delta }} \right)} $$ randomized programs such that one of them is correct on every input, with high probability. Such a strong self-corrector is a useful tool in complexity theory—with some applications known.
Starting Page	365
Ending Page	426
Page Count	62
File Format	PDF
ISSN	02099683
Journal	Combinatorica
Volume Number	23
Issue Number	3
e-ISSN	14396912
Language	English
Publisher	Springer-Verlag
Publisher Date	2003-01-01
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Computational Mathematics

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

Concentration of Multivariate Polynomials and Its Applications

On Improved Bounds for Bounded Degree Spanning Trees for Points in Arbitrary Dimension

Explicit Bounded-Degree Unique-Neighbor Concentrators

Testing Monotonicity

On the minimal fourier degree of symmetric Boolean functions

Degree bounded matroids and submodular flows

Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis

Distinct Distance Estimates and Low Degree Polynomial Partitioning

Improved Pseudorandom Generators for Combinatorial Rectangles

Improved Low-Degree Testing and its Applications

Similar Documents

Concentration of Multivariate Polynomials and Its Applications

On Improved Bounds for Bounded Degree Spanning Trees for Points in Arbitrary Dimension

Explicit Bounded-Degree Unique-Neighbor Concentrators

Testing Monotonicity

On the minimal fourier degree of symmetric Boolean functions

Degree bounded matroids and submodular flows

Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis

Distinct Distance Estimates and Low Degree Polynomial Partitioning

Improved Pseudorandom Generators for Combinatorial Rectangles

Improved Low-Degree Testing and its Applications