Ontology type: schema:Chapter Open Access: True
2009
AUTHORSElena Grigorescu , Tali Kaufman , Madhu Sudan
ABSTRACTMotivated by questions in property testing, we search for linear error-correcting codes that have the “single local orbit” property: they are specified by a single local constraint and its translations under the symmetry group of the code. We show that the dual of every “sparse” binary code whose coordinates are indexed by elements 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}}_{2^n}$\end{document} for prime n, and whose symmetry group includes the group of non-singular affine transformations 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}}_{2^n}$\end{document}, has the single local orbit property. (A code is sparse if it contains polynomially many codewords in its block length.) In particular this class includes the dual-BCH codes for whose duals (BCH codes) simple bases were not known. Our result gives the first short (O(n)-bit, as opposed to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\exp(n)$\end{document}-bit) description of a low-weight basis for BCH codes. If 2n − 1 is a Mersenne prime, then we get that every sparse cyclic code also has the single local orbit. More... »
PAGES534-547
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
ISBN
978-3-642-03684-2
978-3-642-03685-9
http://scigraph.springernature.com/pub.10.1007/978-3-642-03685-9_40
DOIhttp://dx.doi.org/10.1007/978-3-642-03685-9_40
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1043623804
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, Cambridge, MA, USA",
"id": "http://www.grid.ac/institutes/grid.116068.8",
"name": [
"MIT, Cambridge, MA, USA"
],
"type": "Organization"
},
"familyName": "Grigorescu",
"givenName": "Elena",
"id": "sg:person.014612515147.15",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "MIT, Cambridge, MA, USA",
"id": "http://www.grid.ac/institutes/grid.116068.8",
"name": [
"MIT, Cambridge, MA, USA"
],
"type": "Organization"
},
"familyName": "Kaufman",
"givenName": "Tali",
"id": "sg:person.011723444630.05",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011723444630.05"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Microsoft Research, Cambridge, MA, USA",
"id": "http://www.grid.ac/institutes/grid.24488.32",
"name": [
"Microsoft Research, Cambridge, MA, 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"
}
],
"datePublished": "2009",
"datePublishedReg": "2009-01-01",
"description": "Motivated by questions in property testing, we search for linear error-correcting codes that have the \u201csingle local orbit\u201d property: they are specified by a single local constraint and its translations under the symmetry group of the code. We show that the dual of every \u201csparse\u201d binary code whose coordinates are indexed by elements 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}}_{2^n}$\\end{document} for prime n, and whose symmetry group includes the group of non-singular affine transformations 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}}_{2^n}$\\end{document}, has the single local orbit property. (A code is sparse if it contains polynomially many codewords in its block length.) In particular this class includes the dual-BCH codes for whose duals (BCH codes) simple bases were not known. Our result gives the first short (O(n)-bit, as opposed 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}$\\exp(n)$\\end{document}-bit) description of a low-weight basis for BCH codes. If 2n\u2009\u2212\u20091 is a Mersenne prime, then we get that every sparse cyclic code also has the single local orbit.",
"editor": [
{
"familyName": "Dinur",
"givenName": "Irit",
"type": "Person"
},
{
"familyName": "Jansen",
"givenName": "Klaus",
"type": "Person"
},
{
"familyName": "Naor",
"givenName": "Joseph",
"type": "Person"
},
{
"familyName": "Rolim",
"givenName": "Jos\u00e9",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-642-03685-9_40",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-642-03684-2",
"978-3-642-03685-9"
],
"name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques",
"type": "Book"
},
"keywords": [
"primes",
"questions",
"testing",
"error-correcting codes",
"group",
"representation",
"linear error-correcting codes",
"code",
"translation",
"basis",
"results",
"description",
"properties",
"local constraints",
"constraints",
"binary codes",
"coordinates",
"elements",
"affine transformation",
"transformation",
"class",
"simple basis",
"succinct representation",
"applications",
"property testing",
"local orbits",
"orbit",
"symmetry group",
"dual",
"prime n",
"orbit properties",
"dual BCH codes",
"BCH codes",
"Mersenne primes",
"cyclic codes"
],
"name": "Succinct Representation of Codes with Applications to Testing",
"pagination": "534-547",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1043623804"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-642-03685-9_40"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-642-03685-9_40",
"https://app.dimensions.ai/details/publication/pub.1043623804"
],
"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_281.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-642-03685-9_40"
}
]
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-03685-9_40'
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-03685-9_40'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-03685-9_40'
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-03685-9_40'
This table displays all metadata directly associated to this object as RDF triples.
127 TRIPLES
23 PREDICATES
61 URIs
54 LITERALS
7 BLANK NODES
Subject | Predicate | Object | |
---|---|---|---|
1 | sg:pub.10.1007/978-3-642-03685-9_40 | schema:about | anzsrc-for:01 |
2 | ″ | ″ | anzsrc-for:0101 |
3 | ″ | schema:author | N308ff1e6bc8f470984b180de2bcb1c27 |
4 | ″ | schema:datePublished | 2009 |
5 | ″ | schema:datePublishedReg | 2009-01-01 |
6 | ″ | schema:description | Motivated by questions in property testing, we search for linear error-correcting codes that have the “single local orbit” property: they are specified by a single local constraint and its translations under the symmetry group of the code. We show that the dual of every “sparse” binary code whose coordinates are indexed by elements 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}}_{2^n}$\end{document} for prime n, and whose symmetry group includes the group of non-singular affine transformations 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}}_{2^n}$\end{document}, has the single local orbit property. (A code is sparse if it contains polynomially many codewords in its block length.) In particular this class includes the dual-BCH codes for whose duals (BCH codes) simple bases were not known. Our result gives the first short (O(n)-bit, as opposed to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\exp(n)$\end{document}-bit) description of a low-weight basis for BCH codes. If 2n − 1 is a Mersenne prime, then we get that every sparse cyclic code also has the single local orbit. |
7 | ″ | schema:editor | Na33972aa806c431facb26718269e1d13 |
8 | ″ | schema:genre | chapter |
9 | ″ | schema:inLanguage | en |
10 | ″ | schema:isAccessibleForFree | true |
11 | ″ | schema:isPartOf | N49fc3ffb829740c888eeb75edeedaa20 |
12 | ″ | schema:keywords | BCH codes |
13 | ″ | ″ | Mersenne primes |
14 | ″ | ″ | affine transformation |
15 | ″ | ″ | applications |
16 | ″ | ″ | basis |
17 | ″ | ″ | binary codes |
18 | ″ | ″ | class |
19 | ″ | ″ | code |
20 | ″ | ″ | constraints |
21 | ″ | ″ | coordinates |
22 | ″ | ″ | cyclic codes |
23 | ″ | ″ | description |
24 | ″ | ″ | dual |
25 | ″ | ″ | dual BCH codes |
26 | ″ | ″ | elements |
27 | ″ | ″ | error-correcting codes |
28 | ″ | ″ | group |
29 | ″ | ″ | linear error-correcting codes |
30 | ″ | ″ | local constraints |
31 | ″ | ″ | local orbits |
32 | ″ | ″ | orbit |
33 | ″ | ″ | orbit properties |
34 | ″ | ″ | prime n |
35 | ″ | ″ | primes |
36 | ″ | ″ | properties |
37 | ″ | ″ | property testing |
38 | ″ | ″ | questions |
39 | ″ | ″ | representation |
40 | ″ | ″ | results |
41 | ″ | ″ | simple basis |
42 | ″ | ″ | succinct representation |
43 | ″ | ″ | symmetry group |
44 | ″ | ″ | testing |
45 | ″ | ″ | transformation |
46 | ″ | ″ | translation |
47 | ″ | schema:name | Succinct Representation of Codes with Applications to Testing |
48 | ″ | schema:pagination | 534-547 |
49 | ″ | schema:productId | N7f325931bfa24c238d53da03d874014d |
50 | ″ | ″ | Nf3fb413d9e764da6ace9d068f41f7fa3 |
51 | ″ | schema:publisher | N3c22ed8ee2ed4e9bb4fce95d8d3ccfb8 |
52 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1043623804 |
53 | ″ | ″ | https://doi.org/10.1007/978-3-642-03685-9_40 |
54 | ″ | schema:sdDatePublished | 2022-05-20T07:45 |
55 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
56 | ″ | schema:sdPublisher | N97f33682d20e453fa31294a5f999694f |
57 | ″ | schema:url | https://doi.org/10.1007/978-3-642-03685-9_40 |
58 | ″ | sgo:license | sg:explorer/license/ |
59 | ″ | sgo:sdDataset | chapters |
60 | ″ | rdf:type | schema:Chapter |
61 | N02116e3afb744fbb89e7f1fdcdbd38ad | rdf:first | N86ec16f67719476084d1e010eb390dee |
62 | ″ | rdf:rest | Nadcfa086f3fb4033bb2c9a5f846e4287 |
63 | N308ff1e6bc8f470984b180de2bcb1c27 | rdf:first | sg:person.014612515147.15 |
64 | ″ | rdf:rest | N89e50933b8bd447696fea4c2b0f80373 |
65 | N3c22ed8ee2ed4e9bb4fce95d8d3ccfb8 | schema:name | Springer Nature |
66 | ″ | rdf:type | schema:Organisation |
67 | N472dd1b645d14ffc81e22fbfc8b568da | schema:familyName | Naor |
68 | ″ | schema:givenName | Joseph |
69 | ″ | rdf:type | schema:Person |
70 | N49fc3ffb829740c888eeb75edeedaa20 | schema:isbn | 978-3-642-03684-2 |
71 | ″ | ″ | 978-3-642-03685-9 |
72 | ″ | schema:name | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques |
73 | ″ | rdf:type | schema:Book |
74 | N7f325931bfa24c238d53da03d874014d | schema:name | doi |
75 | ″ | schema:value | 10.1007/978-3-642-03685-9_40 |
76 | ″ | rdf:type | schema:PropertyValue |
77 | N86ec16f67719476084d1e010eb390dee | schema:familyName | Jansen |
78 | ″ | schema:givenName | Klaus |
79 | ″ | rdf:type | schema:Person |
80 | N89e50933b8bd447696fea4c2b0f80373 | rdf:first | sg:person.011723444630.05 |
81 | ″ | rdf:rest | Nc413cd55ee634fafbf124d8834a0fc30 |
82 | N97f33682d20e453fa31294a5f999694f | schema:name | Springer Nature - SN SciGraph project |
83 | ″ | rdf:type | schema:Organization |
84 | Na33972aa806c431facb26718269e1d13 | rdf:first | Nf4ecd262841e420bb84b47513aa13ca0 |
85 | ″ | rdf:rest | N02116e3afb744fbb89e7f1fdcdbd38ad |
86 | Nadcfa086f3fb4033bb2c9a5f846e4287 | rdf:first | N472dd1b645d14ffc81e22fbfc8b568da |
87 | ″ | rdf:rest | Nddaf9e28901643aca9b1adc6acf1c6e3 |
88 | Nbd0893b472c240dd841c8a77975ec24a | schema:familyName | Rolim |
89 | ″ | schema:givenName | José |
90 | ″ | rdf:type | schema:Person |
91 | Nc413cd55ee634fafbf124d8834a0fc30 | rdf:first | sg:person.014663420265.17 |
92 | ″ | rdf:rest | rdf:nil |
93 | Nddaf9e28901643aca9b1adc6acf1c6e3 | rdf:first | Nbd0893b472c240dd841c8a77975ec24a |
94 | ″ | rdf:rest | rdf:nil |
95 | Nf3fb413d9e764da6ace9d068f41f7fa3 | schema:name | dimensions_id |
96 | ″ | schema:value | pub.1043623804 |
97 | ″ | rdf:type | schema:PropertyValue |
98 | Nf4ecd262841e420bb84b47513aa13ca0 | schema:familyName | Dinur |
99 | ″ | schema:givenName | Irit |
100 | ″ | rdf:type | schema:Person |
101 | anzsrc-for:01 | schema:inDefinedTermSet | anzsrc-for: |
102 | ″ | schema:name | Mathematical Sciences |
103 | ″ | rdf:type | schema:DefinedTerm |
104 | anzsrc-for:0101 | schema:inDefinedTermSet | anzsrc-for: |
105 | ″ | schema:name | Pure Mathematics |
106 | ″ | rdf:type | schema:DefinedTerm |
107 | sg:person.011723444630.05 | schema:affiliation | grid-institutes:grid.116068.8 |
108 | ″ | schema:familyName | Kaufman |
109 | ″ | schema:givenName | Tali |
110 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011723444630.05 |
111 | ″ | rdf:type | schema:Person |
112 | sg:person.014612515147.15 | schema:affiliation | grid-institutes:grid.116068.8 |
113 | ″ | schema:familyName | Grigorescu |
114 | ″ | schema:givenName | Elena |
115 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15 |
116 | ″ | rdf:type | schema:Person |
117 | sg:person.014663420265.17 | schema:affiliation | grid-institutes:grid.24488.32 |
118 | ″ | schema:familyName | Sudan |
119 | ″ | schema:givenName | Madhu |
120 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17 |
121 | ″ | rdf:type | schema:Person |
122 | grid-institutes:grid.116068.8 | schema:alternateName | MIT, Cambridge, MA, USA |
123 | ″ | schema:name | MIT, Cambridge, MA, USA |
124 | ″ | rdf:type | schema:Organization |
125 | grid-institutes:grid.24488.32 | schema:alternateName | Microsoft Research, Cambridge, MA, USA |
126 | ″ | schema:name | Microsoft Research, Cambridge, MA, USA |
127 | ″ | rdf:type | schema:Organization |