2010
AUTHORSArnab Bhattacharyya , Swastik Kopparty , Grant Schoenebeck , Madhu Sudan , David Zuckerman
ABSTRACTWe consider the problem of testing if a given function \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2$\end{document} is close to any degree d polynomial in n variables, also known as the problem of testing Reed-Muller codes. We are interested in determining the query-complexity of distinguishing with constant probablity between the case where f is a degree d polynomial and the case where f is Ω(1)-far from all degree d polynomials. Alon et al. [AKK+05] proposed and analyzed a natural 2d + 1-query test T0, and showed that it accepts every degree d polynomial with probability 1, while rejecting functions that are Ω(1)-far with probability Ω(1/(d 2d)). This leads to a O(d 4d)-query test for degree d Reed-Muller codes.We give an asymptotically optimal analysis of T0, showing that it rejects functions that are Ω(1)-far with Ω(1)-probability (so the rejection probability is a universal constant independent of d and n). In particular, this implies that the query complexity of testing degree d Reed-Muller codes is O(2d).Our proof works by induction on n, and yields a new analysis of even the classical Blum-Luby-Rubinfeld [BLR93] linearity test, for the setting of functions mapping \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_2^n$\end{document} to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_2$\end{document}. Our results also imply a “query hierarchy” result for property testing of affine-invariant properties: 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 [GKNR08] for graph properties.This is a brief overview of the results in the paper [BKS+09]. More... »
PAGES269-275
Property Testing
ISBN
978-3-642-16366-1
978-3-642-16367-8
http://scigraph.springernature.com/pub.10.1007/978-3-642-16367-8_19
DOIhttp://dx.doi.org/10.1007/978-3-642-16367-8_19
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1052623414
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/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Pure Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "MIT, USA",
"id": "http://www.grid.ac/institutes/grid.116068.8",
"name": [
"MIT, USA"
],
"type": "Organization"
},
"familyName": "Bhattacharyya",
"givenName": "Arnab",
"id": "sg:person.012357145015.18",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357145015.18"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "MIT, USA",
"id": "http://www.grid.ac/institutes/grid.116068.8",
"name": [
"MIT, USA"
],
"type": "Organization"
},
"familyName": "Kopparty",
"givenName": "Swastik",
"id": "sg:person.014276170447.16",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "UC Berkeley, USA",
"id": "http://www.grid.ac/institutes/grid.47840.3f",
"name": [
"UC Berkeley, USA"
],
"type": "Organization"
},
"familyName": "Schoenebeck",
"givenName": "Grant",
"id": "sg:person.01256267073.50",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01256267073.50"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Microsoft Research, USA",
"id": "http://www.grid.ac/institutes/grid.419815.0",
"name": [
"Microsoft Research, USA"
],
"type": "Organization"
},
"familyName": "Sudan",
"givenName": "Madhu",
"id": "sg:person.014663420265.17",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "UT Austin, USA",
"id": "http://www.grid.ac/institutes/grid.89336.37",
"name": [
"UT Austin, USA"
],
"type": "Organization"
},
"familyName": "Zuckerman",
"givenName": "David",
"id": "sg:person.01101524740.75",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01101524740.75"
],
"type": "Person"
}
],
"datePublished": "2010",
"datePublishedReg": "2010-01-01",
"description": "We consider the problem of testing if a given function \\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}$f : \\mathbb{F}_2^n \\rightarrow \\mathbb{F}_2$\\end{document} is close to any degree d polynomial in n variables, also known as the problem of testing Reed-Muller codes. We are interested in determining the query-complexity of distinguishing with constant probablity between the case where f is a degree d polynomial and the case where f is \u03a9(1)-far from all degree d polynomials. Alon et al.\u00a0[AKK+05] proposed and analyzed a natural 2d\u2009+\u20091-query test T0, and showed that it accepts every degree d polynomial with probability 1, while rejecting functions that are \u03a9(1)-far with probability \u03a9(1/(d 2d)). This leads to a O(d 4d)-query test for degree d Reed-Muller codes.We give an asymptotically optimal analysis of T0, showing that it rejects functions that are \u03a9(1)-far with \u03a9(1)-probability (so the rejection probability is a universal constant independent of d and n). In particular, this implies that the query complexity of testing degree d Reed-Muller codes is O(2d).Our proof works by induction on n, and yields a new analysis of even the classical Blum-Luby-Rubinfeld\u00a0[BLR93] linearity test, for the setting of functions mapping \\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}$\\mathbb{F}_2^n$\\end{document} to \\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}$\\mathbb{F}_2$\\end{document}. Our results also imply a \u201cquery hierarchy\u201d result for property testing of affine-invariant properties: 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 [GKNR08] for graph properties.This is a brief overview of the results in the paper\u00a0[BKS+09].",
"editor": [
{
"familyName": "Goldreich",
"givenName": "Oded",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-16367-8_19",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-642-16366-1",
"978-3-642-16367-8"
],
"name": "Property Testing",
"type": "Book"
},
"keywords": [
"Reed-Muller codes",
"query tests",
"query complexity",
"query hierarchy",
"affine-invariant properties",
"graph properties",
"queries",
"function mapping",
"code",
"natural 2D",
"probability 1",
"complexity",
"brief overview",
"optimal analysis",
"hierarchy",
"optimal testing",
"probability",
"proof",
"Rubinfeld",
"polynomials",
"mapping",
"results",
"property testing",
"testing",
"overview",
"function",
"new analysis",
"probablity",
"analysis",
"cases",
"setting",
"variables",
"properties",
"test",
"linearity test",
"analogous results",
"T0",
"induction",
"problem",
"paper",
"degree d polynomials"
],
"name": "Optimal Testing of Reed-Muller Codes",
"pagination": "269-275",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1052623414"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-16367-8_19"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-16367-8_19",
"https://app.dimensions.ai/details/publication/pub.1052623414"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:45",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_295.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-16367-8_19"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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/978-3-642-16367-8_19'
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/978-3-642-16367-8_19'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-16367-8_19'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-16367-8_19'
This table displays all metadata directly associated to this object as RDF triples.
138 TRIPLES
23 PREDICATES
67 URIs
60 LITERALS
7 BLANK NODES
| Subject | Predicate | Object | |
|---|---|---|---|
| 1 | sg:pub.10.1007/978-3-642-16367-8_19 | schema:about | anzsrc-for:01 |
| 2 | ″ | ″ | anzsrc-for:0101 |
| 3 | ″ | schema:author | Ne32a8e466acd46198032c3ed7367bf13 |
| 4 | ″ | schema:datePublished | 2010 |
| 5 | ″ | schema:datePublishedReg | 2010-01-01 |
| 6 | ″ | schema:description | We consider the problem of testing if a given function \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2$\end{document} is close to any degree d polynomial in n variables, also known as the problem of testing Reed-Muller codes. We are interested in determining the query-complexity of distinguishing with constant probablity between the case where f is a degree d polynomial and the case where f is Ω(1)-far from all degree d polynomials. Alon et al. [AKK+05] proposed and analyzed a natural 2d + 1-query test T0, and showed that it accepts every degree d polynomial with probability 1, while rejecting functions that are Ω(1)-far with probability Ω(1/(d 2d)). This leads to a O(d 4d)-query test for degree d Reed-Muller codes.We give an asymptotically optimal analysis of T0, showing that it rejects functions that are Ω(1)-far with Ω(1)-probability (so the rejection probability is a universal constant independent of d and n). In particular, this implies that the query complexity of testing degree d Reed-Muller codes is O(2d).Our proof works by induction on n, and yields a new analysis of even the classical Blum-Luby-Rubinfeld [BLR93] linearity test, for the setting of functions mapping \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_2^n$\end{document} to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_2$\end{document}. Our results also imply a “query hierarchy” result for property testing of affine-invariant properties: 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 [GKNR08] for graph properties.This is a brief overview of the results in the paper [BKS+09]. |
| 7 | ″ | schema:editor | Nc05c828e5e8049dc9d02be86e77feb4d |
| 8 | ″ | schema:genre | chapter |
| 9 | ″ | schema:inLanguage | en |
| 10 | ″ | schema:isAccessibleForFree | true |
| 11 | ″ | schema:isPartOf | N1450a22b6b414f3d9c0dbae934ba4157 |
| 12 | ″ | schema:keywords | Reed-Muller codes |
| 13 | ″ | ″ | Rubinfeld |
| 14 | ″ | ″ | T0 |
| 15 | ″ | ″ | affine-invariant properties |
| 16 | ″ | ″ | analogous results |
| 17 | ″ | ″ | analysis |
| 18 | ″ | ″ | brief overview |
| 19 | ″ | ″ | cases |
| 20 | ″ | ″ | code |
| 21 | ″ | ″ | complexity |
| 22 | ″ | ″ | degree d polynomials |
| 23 | ″ | ″ | function |
| 24 | ″ | ″ | function mapping |
| 25 | ″ | ″ | graph properties |
| 26 | ″ | ″ | hierarchy |
| 27 | ″ | ″ | induction |
| 28 | ″ | ″ | linearity test |
| 29 | ″ | ″ | mapping |
| 30 | ″ | ″ | natural 2D |
| 31 | ″ | ″ | new analysis |
| 32 | ″ | ″ | optimal analysis |
| 33 | ″ | ″ | optimal testing |
| 34 | ″ | ″ | overview |
| 35 | ″ | ″ | paper |
| 36 | ″ | ″ | polynomials |
| 37 | ″ | ″ | probability |
| 38 | ″ | ″ | probability 1 |
| 39 | ″ | ″ | probablity |
| 40 | ″ | ″ | problem |
| 41 | ″ | ″ | proof |
| 42 | ″ | ″ | properties |
| 43 | ″ | ″ | property testing |
| 44 | ″ | ″ | queries |
| 45 | ″ | ″ | query complexity |
| 46 | ″ | ″ | query hierarchy |
| 47 | ″ | ″ | query tests |
| 48 | ″ | ″ | results |
| 49 | ″ | ″ | setting |
| 50 | ″ | ″ | test |
| 51 | ″ | ″ | testing |
| 52 | ″ | ″ | variables |
| 53 | ″ | schema:name | Optimal Testing of Reed-Muller Codes |
| 54 | ″ | schema:pagination | 269-275 |
| 55 | ″ | schema:productId | N3ae64635ecf94ed9be2ebfe9685ac63f |
| 56 | ″ | ″ | N3ffde0551543409fbcffb334c6f2e8a8 |
| 57 | ″ | schema:publisher | Nf21b649acede47cd8e6860bdd5b53e1a |
| 58 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1052623414 |
| 59 | ″ | ″ | https://doi.org/10.1007/978-3-642-16367-8_19 |
| 60 | ″ | schema:sdDatePublished | 2022-05-20T07:45 |
| 61 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
| 62 | ″ | schema:sdPublisher | N3554a6016a39456bb372ed0b557a7abf |
| 63 | ″ | schema:url | https://doi.org/10.1007/978-3-642-16367-8_19 |
| 64 | ″ | sgo:license | sg:explorer/license/ |
| 65 | ″ | sgo:sdDataset | chapters |
| 66 | ″ | rdf:type | schema:Chapter |
| 67 | N1450a22b6b414f3d9c0dbae934ba4157 | schema:isbn | 978-3-642-16366-1 |
| 68 | ″ | ″ | 978-3-642-16367-8 |
| 69 | ″ | schema:name | Property Testing |
| 70 | ″ | rdf:type | schema:Book |
| 71 | N23fe645bdc4c4361b07aaca653983469 | rdf:first | sg:person.01101524740.75 |
| 72 | ″ | rdf:rest | rdf:nil |
| 73 | N3554a6016a39456bb372ed0b557a7abf | schema:name | Springer Nature - SN SciGraph project |
| 74 | ″ | rdf:type | schema:Organization |
| 75 | N3ae64635ecf94ed9be2ebfe9685ac63f | schema:name | doi |
| 76 | ″ | schema:value | 10.1007/978-3-642-16367-8_19 |
| 77 | ″ | rdf:type | schema:PropertyValue |
| 78 | N3ffde0551543409fbcffb334c6f2e8a8 | schema:name | dimensions_id |
| 79 | ″ | schema:value | pub.1052623414 |
| 80 | ″ | rdf:type | schema:PropertyValue |
| 81 | N49f08992de6347b2acc026698c51ff0c | rdf:first | sg:person.01256267073.50 |
| 82 | ″ | rdf:rest | Nc69974c970e64218b45909469b9299ad |
| 83 | N505e18f58c294fc79f5f23b28d19ab63 | schema:familyName | Goldreich |
| 84 | ″ | schema:givenName | Oded |
| 85 | ″ | rdf:type | schema:Person |
| 86 | Nc05c828e5e8049dc9d02be86e77feb4d | rdf:first | N505e18f58c294fc79f5f23b28d19ab63 |
| 87 | ″ | rdf:rest | rdf:nil |
| 88 | Nc69974c970e64218b45909469b9299ad | rdf:first | sg:person.014663420265.17 |
| 89 | ″ | rdf:rest | N23fe645bdc4c4361b07aaca653983469 |
| 90 | Ndb5d60da597149a78dc1047b2eee374c | rdf:first | sg:person.014276170447.16 |
| 91 | ″ | rdf:rest | N49f08992de6347b2acc026698c51ff0c |
| 92 | Ne32a8e466acd46198032c3ed7367bf13 | rdf:first | sg:person.012357145015.18 |
| 93 | ″ | rdf:rest | Ndb5d60da597149a78dc1047b2eee374c |
| 94 | Nf21b649acede47cd8e6860bdd5b53e1a | schema:name | Springer Nature |
| 95 | ″ | rdf:type | schema:Organisation |
| 96 | anzsrc-for:01 | schema:inDefinedTermSet | anzsrc-for: |
| 97 | ″ | schema:name | Mathematical Sciences |
| 98 | ″ | rdf:type | schema:DefinedTerm |
| 99 | anzsrc-for:0101 | schema:inDefinedTermSet | anzsrc-for: |
| 100 | ″ | schema:name | Pure Mathematics |
| 101 | ″ | rdf:type | schema:DefinedTerm |
| 102 | sg:person.01101524740.75 | schema:affiliation | grid-institutes:grid.89336.37 |
| 103 | ″ | schema:familyName | Zuckerman |
| 104 | ″ | schema:givenName | David |
| 105 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01101524740.75 |
| 106 | ″ | rdf:type | schema:Person |
| 107 | sg:person.012357145015.18 | schema:affiliation | grid-institutes:grid.116068.8 |
| 108 | ″ | schema:familyName | Bhattacharyya |
| 109 | ″ | schema:givenName | Arnab |
| 110 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357145015.18 |
| 111 | ″ | rdf:type | schema:Person |
| 112 | sg:person.01256267073.50 | schema:affiliation | grid-institutes:grid.47840.3f |
| 113 | ″ | schema:familyName | Schoenebeck |
| 114 | ″ | schema:givenName | Grant |
| 115 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01256267073.50 |
| 116 | ″ | rdf:type | schema:Person |
| 117 | sg:person.014276170447.16 | schema:affiliation | grid-institutes:grid.116068.8 |
| 118 | ″ | schema:familyName | Kopparty |
| 119 | ″ | schema:givenName | Swastik |
| 120 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16 |
| 121 | ″ | rdf:type | schema:Person |
| 122 | sg:person.014663420265.17 | schema:affiliation | grid-institutes:grid.419815.0 |
| 123 | ″ | schema:familyName | Sudan |
| 124 | ″ | schema:givenName | Madhu |
| 125 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17 |
| 126 | ″ | rdf:type | schema:Person |
| 127 | grid-institutes:grid.116068.8 | schema:alternateName | MIT, USA |
| 128 | ″ | schema:name | MIT, USA |
| 129 | ″ | rdf:type | schema:Organization |
| 130 | grid-institutes:grid.419815.0 | schema:alternateName | Microsoft Research, USA |
| 131 | ″ | schema:name | Microsoft Research, USA |
| 132 | ″ | rdf:type | schema:Organization |
| 133 | grid-institutes:grid.47840.3f | schema:alternateName | UC Berkeley, USA |
| 134 | ″ | schema:name | UC Berkeley, USA |
| 135 | ″ | rdf:type | schema:Organization |
| 136 | grid-institutes:grid.89336.37 | schema:alternateName | UT Austin, USA |
| 137 | ″ | schema:name | UT Austin, USA |
| 138 | ″ | rdf:type | schema:Organization |