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",
"testing",
"cases",
"query complexity",
"optimal testing",
"induction",
"function",
"T0",
"test",
"query hierarchy",
"graph properties",
"setting",
"function mapping",
"code",
"natural 2D",
"results",
"analysis",
"affine-invariant properties",
"probability 1",
"brief overview",
"variables",
"complexity",
"property testing",
"hierarchy",
"overview",
"polynomials",
"proof",
"optimal analysis",
"mapping",
"probability",
"problem",
"Rubinfeld",
"new analysis",
"properties",
"probablity",
"linearity test",
"analogous results",
"paper",
"degree d polynomial",
"d polynomial",
"constant probablity",
"test T0",
"degree d Reed-Muller codes",
"d Reed-Muller codes",
"testing degree d Reed-Muller codes",
"classical Blum-Luby",
"Blum-Luby"
],
"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-01-01T19:22",
"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/chapter/chapter_394.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.
144 TRIPLES
23 PREDICATES
73 URIs
66 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 | N8b9230ed52924cbfaf0f7a6149dc9721 |
| 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 | N4eb4aefac1ae4fb08a37fb94418c8e6c |
| 8 | ″ | schema:genre | chapter |
| 9 | ″ | schema:inLanguage | en |
| 10 | ″ | schema:isAccessibleForFree | true |
| 11 | ″ | schema:isPartOf | N129b7bba0a9548c58483bd7e86faf640 |
| 12 | ″ | schema:keywords | Blum-Luby |
| 13 | ″ | ″ | Reed-Muller codes |
| 14 | ″ | ″ | Rubinfeld |
| 15 | ″ | ″ | T0 |
| 16 | ″ | ″ | affine-invariant properties |
| 17 | ″ | ″ | analogous results |
| 18 | ″ | ″ | analysis |
| 19 | ″ | ″ | brief overview |
| 20 | ″ | ″ | cases |
| 21 | ″ | ″ | classical Blum-Luby |
| 22 | ″ | ″ | code |
| 23 | ″ | ″ | complexity |
| 24 | ″ | ″ | constant probablity |
| 25 | ″ | ″ | d Reed-Muller codes |
| 26 | ″ | ″ | d polynomial |
| 27 | ″ | ″ | degree d Reed-Muller codes |
| 28 | ″ | ″ | degree d polynomial |
| 29 | ″ | ″ | function |
| 30 | ″ | ″ | function mapping |
| 31 | ″ | ″ | graph properties |
| 32 | ″ | ″ | hierarchy |
| 33 | ″ | ″ | induction |
| 34 | ″ | ″ | linearity test |
| 35 | ″ | ″ | mapping |
| 36 | ″ | ″ | natural 2D |
| 37 | ″ | ″ | new analysis |
| 38 | ″ | ″ | optimal analysis |
| 39 | ″ | ″ | optimal testing |
| 40 | ″ | ″ | overview |
| 41 | ″ | ″ | paper |
| 42 | ″ | ″ | polynomials |
| 43 | ″ | ″ | probability |
| 44 | ″ | ″ | probability 1 |
| 45 | ″ | ″ | probablity |
| 46 | ″ | ″ | problem |
| 47 | ″ | ″ | proof |
| 48 | ″ | ″ | properties |
| 49 | ″ | ″ | property testing |
| 50 | ″ | ″ | query complexity |
| 51 | ″ | ″ | query hierarchy |
| 52 | ″ | ″ | results |
| 53 | ″ | ″ | setting |
| 54 | ″ | ″ | test |
| 55 | ″ | ″ | test T0 |
| 56 | ″ | ″ | testing |
| 57 | ″ | ″ | testing degree d Reed-Muller codes |
| 58 | ″ | ″ | variables |
| 59 | ″ | schema:name | Optimal Testing of Reed-Muller Codes |
| 60 | ″ | schema:pagination | 269-275 |
| 61 | ″ | schema:productId | N055f2c97152844418aaefc719d9c0f57 |
| 62 | ″ | ″ | Nc9e347af13114cc9aba05631ce6522a5 |
| 63 | ″ | schema:publisher | N591e2eba4c9c474497458f30d10cda60 |
| 64 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1052623414 |
| 65 | ″ | ″ | https://doi.org/10.1007/978-3-642-16367-8_19 |
| 66 | ″ | schema:sdDatePublished | 2022-01-01T19:22 |
| 67 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
| 68 | ″ | schema:sdPublisher | N864735c9fb6c42ada55a18d98adf3061 |
| 69 | ″ | schema:url | https://doi.org/10.1007/978-3-642-16367-8_19 |
| 70 | ″ | sgo:license | sg:explorer/license/ |
| 71 | ″ | sgo:sdDataset | chapters |
| 72 | ″ | rdf:type | schema:Chapter |
| 73 | N03dc722737504fbda178c2aa1ab3ccab | rdf:first | sg:person.01101524740.75 |
| 74 | ″ | rdf:rest | rdf:nil |
| 75 | N055f2c97152844418aaefc719d9c0f57 | schema:name | doi |
| 76 | ″ | schema:value | 10.1007/978-3-642-16367-8_19 |
| 77 | ″ | rdf:type | schema:PropertyValue |
| 78 | N129b7bba0a9548c58483bd7e86faf640 | schema:isbn | 978-3-642-16366-1 |
| 79 | ″ | ″ | 978-3-642-16367-8 |
| 80 | ″ | schema:name | Property Testing |
| 81 | ″ | rdf:type | schema:Book |
| 82 | N4eb4aefac1ae4fb08a37fb94418c8e6c | rdf:first | Nafeaf006cdf04807be10754717a2d701 |
| 83 | ″ | rdf:rest | rdf:nil |
| 84 | N591e2eba4c9c474497458f30d10cda60 | schema:name | Springer Nature |
| 85 | ″ | rdf:type | schema:Organisation |
| 86 | N864735c9fb6c42ada55a18d98adf3061 | schema:name | Springer Nature - SN SciGraph project |
| 87 | ″ | rdf:type | schema:Organization |
| 88 | N8b9230ed52924cbfaf0f7a6149dc9721 | rdf:first | sg:person.012357145015.18 |
| 89 | ″ | rdf:rest | Na8b7155d8d7d4d7ba9ea99844b1484f2 |
| 90 | Na34148f29e4246029cf5dd8081650cca | rdf:first | sg:person.01256267073.50 |
| 91 | ″ | rdf:rest | Ne934b6a5150f4f20972d062858b356fa |
| 92 | Na8b7155d8d7d4d7ba9ea99844b1484f2 | rdf:first | sg:person.014276170447.16 |
| 93 | ″ | rdf:rest | Na34148f29e4246029cf5dd8081650cca |
| 94 | Nafeaf006cdf04807be10754717a2d701 | schema:familyName | Goldreich |
| 95 | ″ | schema:givenName | Oded |
| 96 | ″ | rdf:type | schema:Person |
| 97 | Nc9e347af13114cc9aba05631ce6522a5 | schema:name | dimensions_id |
| 98 | ″ | schema:value | pub.1052623414 |
| 99 | ″ | rdf:type | schema:PropertyValue |
| 100 | Ne934b6a5150f4f20972d062858b356fa | rdf:first | sg:person.014663420265.17 |
| 101 | ″ | rdf:rest | N03dc722737504fbda178c2aa1ab3ccab |
| 102 | anzsrc-for:01 | schema:inDefinedTermSet | anzsrc-for: |
| 103 | ″ | schema:name | Mathematical Sciences |
| 104 | ″ | rdf:type | schema:DefinedTerm |
| 105 | anzsrc-for:0101 | schema:inDefinedTermSet | anzsrc-for: |
| 106 | ″ | schema:name | Pure Mathematics |
| 107 | ″ | rdf:type | schema:DefinedTerm |
| 108 | sg:person.01101524740.75 | schema:affiliation | grid-institutes:grid.89336.37 |
| 109 | ″ | schema:familyName | Zuckerman |
| 110 | ″ | schema:givenName | David |
| 111 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01101524740.75 |
| 112 | ″ | rdf:type | schema:Person |
| 113 | sg:person.012357145015.18 | schema:affiliation | grid-institutes:grid.116068.8 |
| 114 | ″ | schema:familyName | Bhattacharyya |
| 115 | ″ | schema:givenName | Arnab |
| 116 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357145015.18 |
| 117 | ″ | rdf:type | schema:Person |
| 118 | sg:person.01256267073.50 | schema:affiliation | grid-institutes:grid.47840.3f |
| 119 | ″ | schema:familyName | Schoenebeck |
| 120 | ″ | schema:givenName | Grant |
| 121 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01256267073.50 |
| 122 | ″ | rdf:type | schema:Person |
| 123 | sg:person.014276170447.16 | schema:affiliation | grid-institutes:grid.116068.8 |
| 124 | ″ | schema:familyName | Kopparty |
| 125 | ″ | schema:givenName | Swastik |
| 126 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16 |
| 127 | ″ | rdf:type | schema:Person |
| 128 | sg:person.014663420265.17 | schema:affiliation | grid-institutes:grid.419815.0 |
| 129 | ″ | schema:familyName | Sudan |
| 130 | ″ | schema:givenName | Madhu |
| 131 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17 |
| 132 | ″ | rdf:type | schema:Person |
| 133 | grid-institutes:grid.116068.8 | schema:alternateName | MIT, USA |
| 134 | ″ | schema:name | MIT, USA |
| 135 | ″ | rdf:type | schema:Organization |
| 136 | grid-institutes:grid.419815.0 | schema:alternateName | Microsoft Research, USA |
| 137 | ″ | schema:name | Microsoft Research, USA |
| 138 | ″ | rdf:type | schema:Organization |
| 139 | grid-institutes:grid.47840.3f | schema:alternateName | UC Berkeley, USA |
| 140 | ″ | schema:name | UC Berkeley, USA |
| 141 | ″ | rdf:type | schema:Organization |
| 142 | grid-institutes:grid.89336.37 | schema:alternateName | UT Austin, USA |
| 143 | ″ | schema:name | UT Austin, USA |
| 144 | ″ | rdf:type | schema:Organization |