Improved Low-Degree Testing and its Applications View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2003-07

AUTHORS

Sanjeev Arora*, Madhu Sudan†

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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ 2^{{ - \log ^{{1 - \in }} n}} $$\end{document}. 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \delta = 1/{\left| F \right|}^{ \in } \ll 0.5 $$\end{document}, then the tester/corrector determines δ and generates \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ O{\left( {\frac{1} {\delta }} \right)} $$\end{document} 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ O{\left( {\frac{1} {\delta }} \right)} $$\end{document} 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. More... »

PAGES

365-426

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00493-003-0025-0

DOI

http://dx.doi.org/10.1007/s00493-003-0025-0

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1031113319


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Princeton University, 35 Olden St, 08540, Princeton, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.16750.35", 
          "name": [
            "Department of Computer Science, Princeton University, 35 Olden St, 08540, Princeton, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Arora*", 
        "givenName": "Sanjeev", 
        "id": "sg:person.0703367214.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0703367214.03"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Laboratory for Computer Science, MIT, 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Laboratory for Computer Science, MIT, 02139, Cambridge, MA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sudan\u2020", 
        "givenName": "Madhu", 
        "id": "sg:person.014663420265.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2003-07", 
    "datePublishedReg": "2003-07-01", 
    "description": "NP = PCP(log n, 1) and\nrelated results crucially depend upon the close connection\nbetween the probability with which a function passes a\nlow degree test and the\ndistance of this function to the nearest degree\nd polynomial. In this paper\nwe study a test proposed by Rubinfeld and Sudan [30]. The\nstrongest previously known connection for this test states that\na function passes the test with probability \u03b4 for some \u03b4 >\n7/8 iff the function has agreement \u2248 \u03b4 with a polynomial of\ndegree d. We present a new,\nand surprisingly strong, analysis which shows that the preceding\nstatement is true for arbitrarily small \u2248, provided the field\nsize is polynomially larger than d/\u03b4. The analysis uses a\nversion of Hilbert\nirreducibility, a tool of algebraic geometry.As a consequence we obtain an alternate construction for\nthe following proof system: A constant prover 1-round proof\nsystem for NP languages in which the verifier uses\nO(log n) random bits, receives answers of\nsize O(log\nn) bits, and has an error\nprobability of at most \n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\n2^{{ - \\log ^{{1 -  \\in }} n}} \n$$\\end{document}. Such a proof system,\nwhich implies the NP-hardness of approximating Set Cover to\nwithin \u03a9(log n) factors, has\nalready been obtained by Raz and Safra [29]. Raz and Safra\nobtain their result by giving a strong analysis, in the sense\ndescribed above, of a new low-degree test that they\npresent.A second consequence of our analysis is a self\ntester/corrector for any buggy program that (supposedly)\ncomputes a polynomial over a finite field. If the program is\ncorrect only on \u03b4 fraction of inputs where \n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\n\\delta  = 1/{\\left| F \\right|}^{ \\in }  \\ll 0.5\n$$\\end{document}, then the\ntester/corrector determines \u03b4 and generates \n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\nO{\\left( {\\frac{1}\n{\\delta }} \\right)}\n$$\\end{document} values for every input,\nsuch that one of them is the correct output. In fact, our\nresults yield something stronger: Given the buggy program, we\ncan construct \n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\nO{\\left( {\\frac{1}\n{\\delta }} \\right)}\n$$\\end{document} randomized programs such that one of them is\ncorrect on every input, with high probability. Such a strong\nself-corrector is a useful tool in complexity theory\u2014with some\napplications known.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00493-003-0025-0", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "23"
      }
    ], 
    "keywords": [
      "algebraic geometry", 
      "NP-hardness", 
      "finite field", 
      "related results", 
      "test", 
      "nearest degree", 
      "polynomials", 
      "degree d.", 
      "random bits", 
      "set cover", 
      "low-degree test", 
      "complexity theory", 
      "close connection", 
      "probability", 
      "function", 
      "probability \u03b4", 
      "Hilbert", 
      "alternate construction", 
      "proof system", 
      "strong analysis", 
      "second consequence", 
      "program", 
      "fraction of inputs", 
      "high probability", 
      "useful tool", 
      "results", 
      "connection", 
      "D.", 
      "analysis", 
      "irreducibility", 
      "consequences", 
      "system", 
      "proof", 
      "factors", 
      "input", 
      "theory", 
      "applications", 
      "testing", 
      "NP", 
      "degree test", 
      "degree", 
      "Sudan", 
      "field", 
      "size", 
      "version", 
      "tool", 
      "geometry", 
      "construction", 
      "bits", 
      "error", 
      "Raz", 
      "Safra", 
      "sense", 
      "present", 
      "corrector", 
      "fraction", 
      "correct output", 
      "output", 
      "statements", 
      "answers", 
      "self", 
      "values", 
      "fact", 
      "distance", 
      "Rubinfeld", 
      "agreement", 
      "language", 
      "verifier", 
      "cover", 
      "paper", 
      "low degree test", 
      "NP language", 
      "buggy programs", 
      "low-degree testing", 
      "version of Hilbert", 
      "new low-degree test", 
      "tester/corrector", 
      "tester/corrector determines \u03b4", 
      "corrector determines \u03b4", 
      "determines \u03b4"
    ], 
    "name": "Improved Low-Degree Testing and its Applications", 
    "pagination": "365-426", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1031113319"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00493-003-0025-0"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00493-003-0025-0", 
      "https://app.dimensions.ai/details/publication/pub.1031113319"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-01-01T18:13", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_365.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00493-003-0025-0"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00493-003-0025-0'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00493-003-0025-0'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-003-0025-0'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-003-0025-0'


 

This table displays all metadata directly associated to this object as RDF triples.

148 TRIPLES      21 PREDICATES      106 URIs      98 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00493-003-0025-0 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nac533cc6aac743d6a707808b032da709
4 schema:datePublished 2003-07
5 schema:datePublishedReg 2003-07-01
6 schema:description 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ 2^{{ - \log ^{{1 - \in }} n}} $$\end{document}. 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \delta = 1/{\left| F \right|}^{ \in } \ll 0.5 $$\end{document}, then the tester/corrector determines δ and generates \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ O{\left( {\frac{1} {\delta }} \right)} $$\end{document} 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ O{\left( {\frac{1} {\delta }} \right)} $$\end{document} 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.
7 schema:genre article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N8fb10d1f38bc41d0911402daebf74d0f
11 Ne4c3594ba71b412abc71f92a3070f78c
12 sg:journal.1136493
13 schema:keywords D.
14 Hilbert
15 NP
16 NP language
17 NP-hardness
18 Raz
19 Rubinfeld
20 Safra
21 Sudan
22 agreement
23 algebraic geometry
24 alternate construction
25 analysis
26 answers
27 applications
28 bits
29 buggy programs
30 close connection
31 complexity theory
32 connection
33 consequences
34 construction
35 correct output
36 corrector
37 corrector determines δ
38 cover
39 degree
40 degree d.
41 degree test
42 determines δ
43 distance
44 error
45 fact
46 factors
47 field
48 finite field
49 fraction
50 fraction of inputs
51 function
52 geometry
53 high probability
54 input
55 irreducibility
56 language
57 low degree test
58 low-degree test
59 low-degree testing
60 nearest degree
61 new low-degree test
62 output
63 paper
64 polynomials
65 present
66 probability
67 probability δ
68 program
69 proof
70 proof system
71 random bits
72 related results
73 results
74 second consequence
75 self
76 sense
77 set cover
78 size
79 statements
80 strong analysis
81 system
82 test
83 tester/corrector
84 tester/corrector determines δ
85 testing
86 theory
87 tool
88 useful tool
89 values
90 verifier
91 version
92 version of Hilbert
93 schema:name Improved Low-Degree Testing and its Applications
94 schema:pagination 365-426
95 schema:productId N0d31b95250df4a4783ad8fef5896f9de
96 N233efc4b43024b23aab4a457993ac5a9
97 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031113319
98 https://doi.org/10.1007/s00493-003-0025-0
99 schema:sdDatePublished 2022-01-01T18:13
100 schema:sdLicense https://scigraph.springernature.com/explorer/license/
101 schema:sdPublisher N3f5f29879c8840f5b039b502a97be2a5
102 schema:url https://doi.org/10.1007/s00493-003-0025-0
103 sgo:license sg:explorer/license/
104 sgo:sdDataset articles
105 rdf:type schema:ScholarlyArticle
106 N0d31b95250df4a4783ad8fef5896f9de schema:name dimensions_id
107 schema:value pub.1031113319
108 rdf:type schema:PropertyValue
109 N233efc4b43024b23aab4a457993ac5a9 schema:name doi
110 schema:value 10.1007/s00493-003-0025-0
111 rdf:type schema:PropertyValue
112 N3f5f29879c8840f5b039b502a97be2a5 schema:name Springer Nature - SN SciGraph project
113 rdf:type schema:Organization
114 N54a2a3bc2b8e4c699431d475ae32d6f3 rdf:first sg:person.014663420265.17
115 rdf:rest rdf:nil
116 N8fb10d1f38bc41d0911402daebf74d0f schema:issueNumber 3
117 rdf:type schema:PublicationIssue
118 Nac533cc6aac743d6a707808b032da709 rdf:first sg:person.0703367214.03
119 rdf:rest N54a2a3bc2b8e4c699431d475ae32d6f3
120 Ne4c3594ba71b412abc71f92a3070f78c schema:volumeNumber 23
121 rdf:type schema:PublicationVolume
122 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
123 schema:name Information and Computing Sciences
124 rdf:type schema:DefinedTerm
125 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
126 schema:name Computation Theory and Mathematics
127 rdf:type schema:DefinedTerm
128 sg:journal.1136493 schema:issn 0209-9683
129 1439-6912
130 schema:name Combinatorica
131 schema:publisher Springer Nature
132 rdf:type schema:Periodical
133 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.116068.8
134 schema:familyName Sudan†
135 schema:givenName Madhu
136 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
137 rdf:type schema:Person
138 sg:person.0703367214.03 schema:affiliation grid-institutes:grid.16750.35
139 schema:familyName Arora*
140 schema:givenName Sanjeev
141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0703367214.03
142 rdf:type schema:Person
143 grid-institutes:grid.116068.8 schema:alternateName Laboratory for Computer Science, MIT, 02139, Cambridge, MA, USA
144 schema:name Laboratory for Computer Science, MIT, 02139, Cambridge, MA, USA
145 rdf:type schema:Organization
146 grid-institutes:grid.16750.35 schema:alternateName Department of Computer Science, Princeton University, 35 Olden St, 08540, Princeton, NJ, USA
147 schema:name Department of Computer Science, Princeton University, 35 Olden St, 08540, Princeton, NJ, USA
148 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...