# A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes

Ontology type: schema:Chapter      Open Access: True

### Chapter Info

DATE

2012

AUTHORS ABSTRACT

Over a finite field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb{F}}_q$\end{document} the (n,d,q)-Reed-Muller code is the code given by evaluations of n-variate polynomials of total degree at most d on all points (of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb{F}}_q^n$\end{document}). The task of testing if a 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}}_q^n \to {\mathbb{F}}_q$\end{document} is close to a codeword of an (n,d,q)-Reed-Muller code has been of central interest in complexity theory and property testing. The query complexity of this task is the minimal number of queries that a tester can make (minimum over all testers of the maximum number of queries over all random choices) while accepting all Reed-Muller codewords and rejecting words that are δ-far from the code with probability Ω(δ). (In this work we allow the constant in the Ω to depend on d.)For codes over a prime field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb F}_q$\end{document} the optimal query complexity is well-known and known to be Θ(q⌈(d + 1)/(q − 1)⌉), and the test consists of testing if f is a degree d polynomial on a randomly chosen (⌈(d + 1)/(q − 1) ⌉)-dimensional affine subspace of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb{F}}_q^n$\end{document}. If q is not a prime, then the above quantity remains a lower bound, whereas the previously known upper bound grows to O(q⌈(d + 1)/(q − q/p) ⌉) where p is the characteristic of the field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb{F}}_q$\end{document}. In this work we give a new upper bound of (cq)(d + 1)/q on the query complexity, where c is a universal constant. Thus for every p and sufficiently large q this bound improves over the previously known bound by a polynomial factor.In the process we also give new upper bounds on the “spanning weight” of the dual of the Reed-Muller code (which is also a Reed-Muller code). The spanning weight of a code is the smallest integer w such that codewords of Hamming weight at most w span the code. The main technical contribution of this work is the design of tests that test a function by not querying its value on an entire subspace of the space, but rather on a carefully chosen (algebraically nice) subset of the points from low-dimensional subspaces. More... »

PAGES

639-650

### Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-642-32511-3
978-3-642-32512-0

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-32512-0_54

DOI

http://dx.doi.org/10.1007/978-3-642-32512-0_54

DIMENSIONS

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

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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": "Department of Computer Science, Technion, Haifa, Israel",
"id": "http://www.grid.ac/institutes/grid.6451.6",
"name": [
"Department of Computer Science, Technion, Haifa, Israel"
],
"type": "Organization"
},
"familyName": "Ron-Zewi",
"givenName": "Noga",
"id": "sg:person.013153216765.32",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013153216765.32"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Microsoft Research New England, Cambridge, MA, USA",
"id": "http://www.grid.ac/institutes/None",
"name": [
"Microsoft Research New England, Cambridge, MA, USA"
],
"type": "Organization"
},
"familyName": "Sudan",
"id": "sg:person.014663420265.17",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
],
"type": "Person"
}
],
"datePublished": "2012",
"datePublishedReg": "2012-01-01",
"description": "Over a finite field \\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}}_q$\\end{document} the (n,d,q)-Reed-Muller code is the code given by evaluations of n-variate polynomials of total degree at most d on all points (of \\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}}_q^n$\\end{document}). The task of testing if a 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}}_q^n \\to {\\mathbb{F}}_q$\\end{document} is close to a codeword of an (n,d,q)-Reed-Muller code has been of central interest in complexity theory and property testing. The query complexity of this task is the minimal number of queries that a tester can make (minimum over all testers of the maximum number of queries over all random choices) while accepting all Reed-Muller codewords and rejecting words that are \u03b4-far from the code with probability \u03a9(\u03b4). (In this work we allow the constant in the \u03a9 to depend on d.)For codes over a prime field \\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}_q$\\end{document} the optimal query complexity is well-known and known to be \u0398(q\u2308(d\u2009+\u20091)/(q\u2009\u2212\u20091)\u2309), and the test consists of testing if f is a degree d polynomial on a randomly chosen (\u2308(d\u2009+\u20091)/(q\u2009\u2212\u20091) \u2309)-dimensional affine subspace of \\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}}_q^n$\\end{document}. If q is not a prime, then the above quantity remains a lower bound, whereas the previously known upper bound grows to O(q\u2308(d\u2009+\u20091)/(q\u2009\u2212\u2009q/p) \u2309) where p is the characteristic of the field \\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}}_q$\\end{document}. In this work we give a new upper bound of (cq)(d\u2009+\u20091)/q on the query complexity, where c is a universal constant. Thus for every p and sufficiently large q this bound improves over the previously known bound by a polynomial factor.In the process we also give new upper bounds on the \u201cspanning weight\u201d of the dual of the Reed-Muller code (which is also a Reed-Muller code). The spanning weight of a code is the smallest integer w such that codewords of Hamming weight at most w span the code. The main technical contribution of this work is the design of tests that test a function by not querying its value on an entire subspace of the space, but rather on a carefully chosen (algebraically nice) subset of the points from low-dimensional subspaces.",
"editor": [
{
"familyName": "Gupta",
"givenName": "Anupam",
"type": "Person"
},
{
"familyName": "Jansen",
"givenName": "Klaus",
"type": "Person"
},
{
"familyName": "Rolim",
"givenName": "Jos\u00e9",
"type": "Person"
},
{
"familyName": "Servedio",
"givenName": "Rocco",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-32512-0_54",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-642-32511-3",
"978-3-642-32512-0"
],
"name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques",
"type": "Book"
},
"keywords": [
"query complexity",
"Reed-Muller codes",
"low-dimensional subspace",
"Muller codes",
"main technical contribution",
"optimal query complexity",
"new upper bounds",
"technical contribution",
"prime fields",
"upper bounds",
"design of tests",
"codewords",
"complexity theory",
"complexity",
"finite field",
"code",
"polynomial factor",
"Hamming weight",
"subspace",
"minimal number",
"queries",
"affine subspace",
"property testing",
"bounds",
"work",
"variate polynomials",
"generalized Reed\u2013Muller codes",
"polynomials",
"point",
"grows",
"design",
"space",
"field",
"testing",
"words",
"tester",
"probability",
"subset",
"evaluation",
"total degree",
"interest",
"number",
"process",
"function",
"central interest",
"contribution",
"theory",
"characteristics",
"weight",
"primes",
"degree",
"test",
"quantity",
"dual",
"values",
"above quantities",
"span",
"factors",
"constants",
"universal constant",
"degree d polynomial",
"entire subspace",
"Reed-Muller codewords",
"d polynomial",
"Testing Generalized Reed-Muller codes"
],
"name": "A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes",
"pagination": "639-650",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1024843922"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-32512-0_54"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-32512-0_54",
"https://app.dimensions.ai/details/publication/pub.1024843922"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-01-01T19:09",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_16.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-32512-0_54"
}
]

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-32512-0_54'

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-32512-0_54'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-32512-0_54'

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-32512-0_54'

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

152 TRIPLES      23 PREDICATES      93 URIs      86 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0101
3 schema:author N04ddb6d4d138471cb8af2ff851464851
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description Over a finite field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb{F}}_q$\end{document} the (n,d,q)-Reed-Muller code is the code given by evaluations of n-variate polynomials of total degree at most d on all points (of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb{F}}_q^n$\end{document}). The task of testing if a 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}}_q^n \to {\mathbb{F}}_q$\end{document} is close to a codeword of an (n,d,q)-Reed-Muller code has been of central interest in complexity theory and property testing. The query complexity of this task is the minimal number of queries that a tester can make (minimum over all testers of the maximum number of queries over all random choices) while accepting all Reed-Muller codewords and rejecting words that are δ-far from the code with probability Ω(δ). (In this work we allow the constant in the Ω to depend on d.)For codes over a prime field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb F}_q$\end{document} the optimal query complexity is well-known and known to be Θ(q⌈(d + 1)/(q − 1)⌉), and the test consists of testing if f is a degree d polynomial on a randomly chosen (⌈(d + 1)/(q − 1) ⌉)-dimensional affine subspace of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb{F}}_q^n$\end{document}. If q is not a prime, then the above quantity remains a lower bound, whereas the previously known upper bound grows to O(q⌈(d + 1)/(q − q/p) ⌉) where p is the characteristic of the field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}${\mathbb{F}}_q$\end{document}. In this work we give a new upper bound of (cq)(d + 1)/q on the query complexity, where c is a universal constant. Thus for every p and sufficiently large q this bound improves over the previously known bound by a polynomial factor.In the process we also give new upper bounds on the “spanning weight” of the dual of the Reed-Muller code (which is also a Reed-Muller code). The spanning weight of a code is the smallest integer w such that codewords of Hamming weight at most w span the code. The main technical contribution of this work is the design of tests that test a function by not querying its value on an entire subspace of the space, but rather on a carefully chosen (algebraically nice) subset of the points from low-dimensional subspaces.
7 schema:editor N96c8c58903af4f0185ec4c1426626194
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N18f3e0f5d1c14687a7d99ddc5bda321c
12 schema:keywords Hamming weight
13 Muller codes
14 Reed-Muller codes
15 Reed-Muller codewords
16 Testing Generalized Reed-Muller codes
17 above quantities
18 affine subspace
19 bounds
20 central interest
21 characteristics
22 code
23 codewords
24 complexity
25 complexity theory
26 constants
27 contribution
28 d polynomial
29 degree
30 degree d polynomial
31 design
32 design of tests
33 dual
34 entire subspace
35 evaluation
36 factors
37 field
38 finite field
39 function
40 generalized Reed–Muller codes
41 grows
42 interest
43 low-dimensional subspace
44 main technical contribution
45 minimal number
46 new upper bounds
47 number
48 optimal query complexity
49 point
50 polynomial factor
51 polynomials
52 prime fields
53 primes
54 probability
55 process
56 property testing
57 quantity
58 queries
59 query complexity
60 space
61 span
62 subset
63 subspace
66 technical contribution
67 test
68 tester
69 testing
70 theory
71 total degree
72 universal constant
73 upper bounds
74 values
75 variate polynomials
76 weight
77 words
78 work
79 schema:name A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes
80 schema:pagination 639-650
81 schema:productId N0824db62417b45b5a3c561d80913a533
82 Nbc89026d47f644e388fef430bd7e2d82
83 schema:publisher N8dc0b0b08d1d4eb8a6197a6173fef6b5
84 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024843922
85 https://doi.org/10.1007/978-3-642-32512-0_54
86 schema:sdDatePublished 2022-01-01T19:09
89 schema:url https://doi.org/10.1007/978-3-642-32512-0_54
91 sgo:sdDataset chapters
92 rdf:type schema:Chapter
93 N04ddb6d4d138471cb8af2ff851464851 rdf:first sg:person.013153216765.32
94 rdf:rest Nf462945da6d649a993f9c6060ba9cf9d
95 N0824db62417b45b5a3c561d80913a533 schema:name dimensions_id
96 schema:value pub.1024843922
97 rdf:type schema:PropertyValue
98 N18f3e0f5d1c14687a7d99ddc5bda321c schema:isbn 978-3-642-32511-3
99 978-3-642-32512-0
100 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
101 rdf:type schema:Book
102 N20bdc93ce6644aefbf240f0f3d37f828 schema:familyName Jansen
103 schema:givenName Klaus
104 rdf:type schema:Person
105 N2ad7456100e24325a9e718d0cc2610f6 schema:name Springer Nature - SN SciGraph project
106 rdf:type schema:Organization
108 schema:givenName José
109 rdf:type schema:Person
110 N6622d2052588439abde64af7e87b2df7 rdf:first N20bdc93ce6644aefbf240f0f3d37f828
111 rdf:rest Nc42eb9c6f95b42d8824e0411df27a13c
113 rdf:rest rdf:nil
114 N8dc0b0b08d1d4eb8a6197a6173fef6b5 schema:name Springer Nature
115 rdf:type schema:Organisation
116 N96c8c58903af4f0185ec4c1426626194 rdf:first Nacd07ea42c224059a43c2835983e8fa2
117 rdf:rest N6622d2052588439abde64af7e87b2df7
118 Nacd07ea42c224059a43c2835983e8fa2 schema:familyName Gupta
119 schema:givenName Anupam
120 rdf:type schema:Person
121 Nbc89026d47f644e388fef430bd7e2d82 schema:name doi
122 schema:value 10.1007/978-3-642-32512-0_54
123 rdf:type schema:PropertyValue
125 rdf:rest N8a509b53f5674087be88e3acdaa53047
127 schema:givenName Rocco
128 rdf:type schema:Person
129 Nf462945da6d649a993f9c6060ba9cf9d rdf:first sg:person.014663420265.17
130 rdf:rest rdf:nil
131 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
132 schema:name Mathematical Sciences
133 rdf:type schema:DefinedTerm
134 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
135 schema:name Pure Mathematics
136 rdf:type schema:DefinedTerm
137 sg:person.013153216765.32 schema:affiliation grid-institutes:grid.6451.6
138 schema:familyName Ron-Zewi
139 schema:givenName Noga
140 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013153216765.32
141 rdf:type schema:Person
142 sg:person.014663420265.17 schema:affiliation grid-institutes:None
143 schema:familyName Sudan
145 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
146 rdf:type schema:Person
147 grid-institutes:None schema:alternateName Microsoft Research New England, Cambridge, MA, USA
148 schema:name Microsoft Research New England, Cambridge, MA, USA
149 rdf:type schema:Organization
150 grid-institutes:grid.6451.6 schema:alternateName Department of Computer Science, Technion, Haifa, Israel
151 schema:name Department of Computer Science, Technion, Haifa, Israel
152 rdf:type schema:Organization