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", 
      "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

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.

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
 




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


...