# Linear Consistency Testing

Ontology type: schema:Chapter

### Chapter Info

DATE

1999

AUTHORS ABSTRACT

We extend the notion of linearity testing to the task of checking linear-consistency of multiple functions. Informally, functions are “linear” if their graphs form straight lines on the plane. Two such functions are “consistent” if the lines have the same slope. We propose a variant of a test of Blum, Luby and Rubinfeld [8] to check the linear-consistency of three functions f1,f2,f3 mapping a finite Abelian group G to an Abelian group H: Pick x,y ∈ G uniformly and independently at random and check if f1(x) + f2(y) = f3(x + y). We analyze this test for two cases: (1) G and H are arbitrary Abelian groups and (2) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$G = \mathbb{F}^n_2$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$H = \mathbb{F}_2$\end{document}.Questions bearing close relationship to linear-consistency testing seem to have been implicitly considered in recent work on the construction of PCPs (and in particular in the work of Håstad [9]). It is abstracted explicitly for the first time here. We give an application of this problem (and of our results): A (yet another) new and tight characterization of NP, namely ∀ ε > 0. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathrm{NP} = \mathrm{MIP}_{1-\epsilon,\frac{1}{2}}[=(\log n),3,1]$\end{document} I.e., every language in NP has 3-prover 1-round proof systems in which the verifier tosses O(log n) coins and asks each of the three provers one question each. The provers respond with one bit each such that the verifier accepts instance of the language with probability 1– ε and rejects non-instances with probability at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{1}{2}$\end{document}. Such a result is of some interest in the study of probabilistically checkable proofs. More... »

PAGES

109-120

### Book

TITLE

Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-540-66329-4
978-3-540-48413-4

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-48413-4_11

DOI

http://dx.doi.org/10.1007/978-3-540-48413-4_11

DIMENSIONS

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

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/17",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Psychology and Cognitive Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1701",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Psychology",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Department of Mathematics and Computer Science, Bar-Ilan University, 52900, Ramat-Gan, Israel",
"id": "http://www.grid.ac/institutes/grid.22098.31",
"name": [
"Department of Mathematics and Computer Science, Bar-Ilan University, 52900, Ramat-Gan, Israel"
],
"type": "Organization"
},
"familyName": "Aumann",
"givenName": "Yonatan",
"id": "sg:person.015202435666.27",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015202435666.27"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, Sweden",
"id": "http://www.grid.ac/institutes/grid.5037.1",
"name": [
"Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, Sweden"
],
"type": "Organization"
},
"givenName": "Johan",
"id": "sg:person.011562747461.61",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011562747461.61"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Institute of Computer Science, Hebrew University, Jerusalem, Israel",
"id": "http://www.grid.ac/institutes/grid.9619.7",
"name": [
"DEAS, Harvard University, 02138, Cambridge, MA, USA",
"Institute of Computer Science, Hebrew University, Jerusalem, Israel"
],
"type": "Organization"
},
"familyName": "Rabin",
"givenName": "Michael O.",
"id": "sg:person.07630161153.11",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07630161153.11"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Electrical Engineering and Computer Science, MIT, 545 Technology Square, 02139, Cambridge, MA, USA",
"id": "http://www.grid.ac/institutes/grid.116068.8",
"name": [
"Department of Electrical Engineering and Computer Science, MIT, 545 Technology Square, 02139, 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": "1999",
"datePublishedReg": "1999-01-01",
"description": "We extend the notion of linearity testing to the task of checking linear-consistency of multiple functions. Informally, functions are \u201clinear\u201d if their graphs form straight lines on the plane. Two such functions are \u201cconsistent\u201d if the lines have the same slope. We propose a variant of a test of Blum, Luby and Rubinfeld [8] to check the linear-consistency of three functions\u00a0f1,f2,f3 mapping a finite Abelian group\u00a0G to an Abelian group\u00a0H: Pick x,y \u2208 G uniformly and independently at random and check if\u00a0 f1(x) + f2(y) = f3(x + y). We analyze this test for two cases: (1)\u00a0G and\u00a0H are arbitrary Abelian groups and (2) \\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}$G = \\mathbb{F}^n_2$\\end{document} and \\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}$H = \\mathbb{F}_2$\\end{document}.Questions bearing close relationship to linear-consistency testing seem to have been implicitly considered in recent work on the construction of PCPs (and in particular in the work of H\u00e5stad [9]). It is abstracted explicitly for the first time here. We give an application of this problem (and of our results): A (yet another) new and tight characterization of NP, namely \u2200 \u03b5 > 0. \\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}$\\mathrm{NP} = \\mathrm{MIP}_{1-\\epsilon,\\frac{1}{2}}[=(\\log n),3,1]$\\end{document} I.e., every language in NP has 3-prover 1-round proof systems in which the verifier tosses O(log n) coins and asks each of the three provers one question each. The provers respond with one bit each such that the verifier accepts instance of the language with probability 1\u2013 \u03b5 and rejects non-instances with probability at least \\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}$\\frac{1}{2}$\\end{document}. Such a result is of some interest in the study of probabilistically checkable proofs.",
"editor": [
{
"familyName": "Hochbaum",
"givenName": "Dorit S.",
"type": "Person"
},
{
"familyName": "Jansen",
"givenName": "Klaus",
"type": "Person"
},
{
"familyName": "Rolim",
"givenName": "Jos\u00e9 D. P.",
"type": "Person"
},
{
"familyName": "Sinclair",
"givenName": "Alistair",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-48413-4_11",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-66329-4",
"978-3-540-48413-4"
],
"name": "Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques",
"type": "Book"
},
"keywords": [
"group",
"testing",
"multiple functions",
"test",
"function",
"PCP",
"close relationship",
"lines",
"study",
"variants",
"cases",
"first time",
"questions",
"relationship",
"time",
"one question",
"results",
"consistency testing",
"recent work",
"toss",
"same slope",
"instances",
"interest",
"probability",
"such functions",
"characterization",
"system",
"slope",
"problem",
"coins",
"proof",
"work",
"NP",
"language",
"notion",
"straight line",
"applications",
"linearity testing",
"plane",
"abelian groups",
"Blum",
"arbitrary Abelian group",
"finite abelian group",
"construction",
"probability 1",
"graph",
"bits",
"checkable proofs",
"proof system",
"tight characterization",
"Luby",
"provers",
"verifier",
"Rubinfeld",
"test of Blum",
"Pick x",
"linear-consistency testing",
"construction of PCPs",
"verifier tosses",
"provers one question",
"Linear Consistency Testing"
],
"name": "Linear Consistency Testing",
"pagination": "109-120",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1006067612"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-48413-4_11"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-48413-4_11",
"https://app.dimensions.ai/details/publication/pub.1006067612"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-01-01T19:13",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_222.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-540-48413-4_11"
}
]

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-540-48413-4_11'

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-540-48413-4_11'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-48413-4_11'

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-540-48413-4_11'

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

168 TRIPLES      23 PREDICATES      87 URIs      80 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:1701
3 schema:author N93300434fda7409790a6ae2c4767767c
4 schema:datePublished 1999
5 schema:datePublishedReg 1999-01-01
6 schema:description We extend the notion of linearity testing to the task of checking linear-consistency of multiple functions. Informally, functions are “linear” if their graphs form straight lines on the plane. Two such functions are “consistent” if the lines have the same slope. We propose a variant of a test of Blum, Luby and Rubinfeld [8] to check the linear-consistency of three functions f1,f2,f3 mapping a finite Abelian group G to an Abelian group H: Pick x,y ∈ G uniformly and independently at random and check if  f1(x) + f2(y) = f3(x + y). We analyze this test for two cases: (1) G and H are arbitrary Abelian groups and (2) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$G = \mathbb{F}^n_2$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$H = \mathbb{F}_2$\end{document}.Questions bearing close relationship to linear-consistency testing seem to have been implicitly considered in recent work on the construction of PCPs (and in particular in the work of Håstad [9]). It is abstracted explicitly for the first time here. We give an application of this problem (and of our results): A (yet another) new and tight characterization of NP, namely ∀ ε > 0. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathrm{NP} = \mathrm{MIP}_{1-\epsilon,\frac{1}{2}}[=(\log n),3,1]$\end{document} I.e., every language in NP has 3-prover 1-round proof systems in which the verifier tosses O(log n) coins and asks each of the three provers one question each. The provers respond with one bit each such that the verifier accepts instance of the language with probability 1– ε and rejects non-instances with probability at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\frac{1}{2}$\end{document}. Such a result is of some interest in the study of probabilistically checkable proofs.
7 schema:editor N25429b8590304d8594f985ff874e0152
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N9bf889cc012c4cb483e243d759133fdc
12 schema:keywords Blum
13 Linear Consistency Testing
14 Luby
15 NP
16 PCP
17 Pick x
18 Rubinfeld
19 abelian groups
20 applications
21 arbitrary Abelian group
22 bits
23 cases
24 characterization
25 checkable proofs
26 close relationship
27 coins
28 consistency testing
29 construction
30 construction of PCPs
31 finite abelian group
32 first time
33 function
34 graph
35 group
36 instances
37 interest
38 language
39 linear-consistency testing
40 linearity testing
41 lines
42 multiple functions
43 notion
44 one question
45 plane
46 probability
47 probability 1
48 problem
49 proof
50 proof system
51 provers
52 provers one question
53 questions
54 recent work
55 relationship
56 results
57 same slope
58 slope
59 straight line
60 study
61 such functions
62 system
64 test
65 test of Blum
66 testing
67 tight characterization
68 time
69 toss
70 variants
71 verifier
72 verifier tosses
73 work
74 schema:name Linear Consistency Testing
75 schema:pagination 109-120
76 schema:productId Na9a480e241ba46018b32f9e24d909ce6
78 schema:publisher Ndf0f6a8e2f2b48fb8755ca4384a9a535
79 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006067612
80 https://doi.org/10.1007/978-3-540-48413-4_11
81 schema:sdDatePublished 2022-01-01T19:13
83 schema:sdPublisher Nb96f8252f7e24547ac428edbc984f028
84 schema:url https://doi.org/10.1007/978-3-540-48413-4_11
86 sgo:sdDataset chapters
87 rdf:type schema:Chapter
88 N043b43eeb1134197b2ab70d03d213a52 rdf:first sg:person.014663420265.17
89 rdf:rest rdf:nil
90 N25429b8590304d8594f985ff874e0152 rdf:first N28ea9aa94e5843a1ab8cd7ba98589023
91 rdf:rest N3016e19b24ec44fabb22e4d2d5a81ba9
92 N28ea9aa94e5843a1ab8cd7ba98589023 schema:familyName Hochbaum
93 schema:givenName Dorit S.
94 rdf:type schema:Person
95 N3016e19b24ec44fabb22e4d2d5a81ba9 rdf:first Nb3c411e36693404b8f84f53493da160f
96 rdf:rest N9d752ed9d8db41faabe00394ea2a93fb
97 N36bc731ee05946b1a7993c8faf418810 rdf:first N74e09448a63e4e309d862e75018b8236
98 rdf:rest rdf:nil
99 N74e09448a63e4e309d862e75018b8236 schema:familyName Sinclair
100 schema:givenName Alistair
101 rdf:type schema:Person
102 N93300434fda7409790a6ae2c4767767c rdf:first sg:person.015202435666.27
103 rdf:rest Nb5dc6fa6cdbc4e718371e60391efdc5c
104 N9bf889cc012c4cb483e243d759133fdc schema:isbn 978-3-540-48413-4
105 978-3-540-66329-4
106 schema:name Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques
107 rdf:type schema:Book
108 N9d752ed9d8db41faabe00394ea2a93fb rdf:first Nd7b5090ce1484c6680220cfe2e4bf45f
109 rdf:rest N36bc731ee05946b1a7993c8faf418810
110 Na9a480e241ba46018b32f9e24d909ce6 schema:name doi
111 schema:value 10.1007/978-3-540-48413-4_11
112 rdf:type schema:PropertyValue
113 Nb3c411e36693404b8f84f53493da160f schema:familyName Jansen
114 schema:givenName Klaus
115 rdf:type schema:Person
116 Nb5dc6fa6cdbc4e718371e60391efdc5c rdf:first sg:person.011562747461.61
117 rdf:rest Ne707d6b5dcd241c28e616c69cc9f65e7
118 Nb96f8252f7e24547ac428edbc984f028 schema:name Springer Nature - SN SciGraph project
119 rdf:type schema:Organization
121 schema:value pub.1006067612
122 rdf:type schema:PropertyValue
123 Nd7b5090ce1484c6680220cfe2e4bf45f schema:familyName Rolim
124 schema:givenName José D. P.
125 rdf:type schema:Person
126 Ndf0f6a8e2f2b48fb8755ca4384a9a535 schema:name Springer Nature
127 rdf:type schema:Organisation
128 Ne707d6b5dcd241c28e616c69cc9f65e7 rdf:first sg:person.07630161153.11
129 rdf:rest N043b43eeb1134197b2ab70d03d213a52
130 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
131 schema:name Psychology and Cognitive Sciences
132 rdf:type schema:DefinedTerm
133 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
134 schema:name Psychology
135 rdf:type schema:DefinedTerm
136 sg:person.011562747461.61 schema:affiliation grid-institutes:grid.5037.1
138 schema:givenName Johan
139 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011562747461.61
140 rdf:type schema:Person
141 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.116068.8
142 schema:familyName Sudan
144 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
145 rdf:type schema:Person
146 sg:person.015202435666.27 schema:affiliation grid-institutes:grid.22098.31
147 schema:familyName Aumann
148 schema:givenName Yonatan
149 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015202435666.27
150 rdf:type schema:Person
151 sg:person.07630161153.11 schema:affiliation grid-institutes:grid.9619.7
152 schema:familyName Rabin
153 schema:givenName Michael O.
154 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07630161153.11
155 rdf:type schema:Person
156 grid-institutes:grid.116068.8 schema:alternateName Department of Electrical Engineering and Computer Science, MIT, 545 Technology Square, 02139, Cambridge, MA, USA
157 schema:name Department of Electrical Engineering and Computer Science, MIT, 545 Technology Square, 02139, Cambridge, MA, USA
158 rdf:type schema:Organization
159 grid-institutes:grid.22098.31 schema:alternateName Department of Mathematics and Computer Science, Bar-Ilan University, 52900, Ramat-Gan, Israel
160 schema:name Department of Mathematics and Computer Science, Bar-Ilan University, 52900, Ramat-Gan, Israel
161 rdf:type schema:Organization
162 grid-institutes:grid.5037.1 schema:alternateName Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, Sweden
163 schema:name Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, Sweden
164 rdf:type schema:Organization
165 grid-institutes:grid.9619.7 schema:alternateName Institute of Computer Science, Hebrew University, Jerusalem, Israel
166 schema:name DEAS, Harvard University, 02138, Cambridge, MA, USA
167 Institute of Computer Science, Hebrew University, Jerusalem, Israel
168 rdf:type schema:Organization