Optimal Testing of Reed-Muller Codes View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Arnab Bhattacharyya , Swastik Kopparty , Grant Schoenebeck , Madhu Sudan , David Zuckerman

ABSTRACT

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]. More... »

PAGES

269-275

Book

TITLE

Property Testing

ISBN

978-3-642-16366-1
978-3-642-16367-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-16367-8_19

DOI

http://dx.doi.org/10.1007/978-3-642-16367-8_19

DIMENSIONS

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


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/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

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/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
 




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


...