Succinct Representation of Codes with Applications to Testing View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Elena Grigorescu , Tali Kaufman , Madhu Sudan

ABSTRACT

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

PAGES

534-547

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-642-03684-2
978-3-642-03685-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-03685-9_40

DOI

http://dx.doi.org/10.1007/978-3-642-03685-9_40

DIMENSIONS

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


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, 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/None", 
          "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": [
      "symmetry group", 
      "linear error-correcting codes", 
      "error-correcting codes", 
      "prime n", 
      "local constraints", 
      "orbit properties", 
      "Mersenne primes", 
      "cyclic codes", 
      "succinct representation", 
      "simple basis", 
      "BCH codes", 
      "orbit", 
      "affine transformation", 
      "binary codes", 
      "dual", 
      "code", 
      "constraints", 
      "coordinates", 
      "class", 
      "representation", 
      "property testing", 
      "primes", 
      "properties", 
      "description", 
      "applications", 
      "transformation", 
      "basis", 
      "elements", 
      "results", 
      "questions", 
      "testing", 
      "translation", 
      "group", 
      "single local orbit", 
      "local orbits", 
      "single local constraint", 
      "non-singular affine transformations", 
      "single local orbit property", 
      "local orbit property", 
      "dual-BCH codes", 
      "duals (BCH codes) simple bases", 
      "low-weight basis", 
      "sparse cyclic code"
    ], 
    "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-01-01T19:09", 
    "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_157.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

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

135 TRIPLES      23 PREDICATES      69 URIs      62 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 N376d794effed4c79bdbdcfaa5b463f83
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 Ne9bba333c0954250ab698a279c20c9af
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N65604f9599894e0694cda57ffc61fe39
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 duals (BCH codes) simple bases
27 elements
28 error-correcting codes
29 group
30 linear error-correcting codes
31 local constraints
32 local orbit property
33 local orbits
34 low-weight basis
35 non-singular affine transformations
36 orbit
37 orbit properties
38 prime n
39 primes
40 properties
41 property testing
42 questions
43 representation
44 results
45 simple basis
46 single local constraint
47 single local orbit
48 single local orbit property
49 sparse cyclic code
50 succinct representation
51 symmetry group
52 testing
53 transformation
54 translation
55 schema:name Succinct Representation of Codes with Applications to Testing
56 schema:pagination 534-547
57 schema:productId N35edc4720e5a4458bf8e55e016d6e19e
58 Na8bb850cc1fa4267b31cb6955df0dd0b
59 schema:publisher N05f66c7a63c8480babed1326f7985e56
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043623804
61 https://doi.org/10.1007/978-3-642-03685-9_40
62 schema:sdDatePublished 2022-01-01T19:09
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N5c98c2a6055044d4acdf2652dad4c97e
65 schema:url https://doi.org/10.1007/978-3-642-03685-9_40
66 sgo:license sg:explorer/license/
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N05f66c7a63c8480babed1326f7985e56 schema:name Springer Nature
70 rdf:type schema:Organisation
71 N0f15451501754c6480a1f34ef66c407f rdf:first sg:person.014663420265.17
72 rdf:rest rdf:nil
73 N1922b5f5ac724e8488a5d89eb3cb9cd0 rdf:first sg:person.011723444630.05
74 rdf:rest N0f15451501754c6480a1f34ef66c407f
75 N23f364f4d5fc452084e9ada63552328f rdf:first N2fa54929e871452d8efdf52ff38dac74
76 rdf:rest Ncea841ce3db44208b5591d97db2019e8
77 N2fa54929e871452d8efdf52ff38dac74 schema:familyName Naor
78 schema:givenName Joseph
79 rdf:type schema:Person
80 N35edc4720e5a4458bf8e55e016d6e19e schema:name doi
81 schema:value 10.1007/978-3-642-03685-9_40
82 rdf:type schema:PropertyValue
83 N376d794effed4c79bdbdcfaa5b463f83 rdf:first sg:person.014612515147.15
84 rdf:rest N1922b5f5ac724e8488a5d89eb3cb9cd0
85 N5c98c2a6055044d4acdf2652dad4c97e schema:name Springer Nature - SN SciGraph project
86 rdf:type schema:Organization
87 N65604f9599894e0694cda57ffc61fe39 schema:isbn 978-3-642-03684-2
88 978-3-642-03685-9
89 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
90 rdf:type schema:Book
91 N96223cceccbe46abb26e874664f6d378 schema:familyName Dinur
92 schema:givenName Irit
93 rdf:type schema:Person
94 Na8bb850cc1fa4267b31cb6955df0dd0b schema:name dimensions_id
95 schema:value pub.1043623804
96 rdf:type schema:PropertyValue
97 Nbbdcf51a97a44fde995a64ae7323bc20 rdf:first Nf4651b9a1d7e4655b404b303fa196830
98 rdf:rest N23f364f4d5fc452084e9ada63552328f
99 Ncea841ce3db44208b5591d97db2019e8 rdf:first Nda32a4d537db47bdb6f13302f501417b
100 rdf:rest rdf:nil
101 Nda32a4d537db47bdb6f13302f501417b schema:familyName Rolim
102 schema:givenName José
103 rdf:type schema:Person
104 Ne9bba333c0954250ab698a279c20c9af rdf:first N96223cceccbe46abb26e874664f6d378
105 rdf:rest Nbbdcf51a97a44fde995a64ae7323bc20
106 Nf4651b9a1d7e4655b404b303fa196830 schema:familyName Jansen
107 schema:givenName Klaus
108 rdf:type schema:Person
109 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
110 schema:name Mathematical Sciences
111 rdf:type schema:DefinedTerm
112 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
113 schema:name Pure Mathematics
114 rdf:type schema:DefinedTerm
115 sg:person.011723444630.05 schema:affiliation grid-institutes:grid.116068.8
116 schema:familyName Kaufman
117 schema:givenName Tali
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011723444630.05
119 rdf:type schema:Person
120 sg:person.014612515147.15 schema:affiliation grid-institutes:grid.116068.8
121 schema:familyName Grigorescu
122 schema:givenName Elena
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15
124 rdf:type schema:Person
125 sg:person.014663420265.17 schema:affiliation grid-institutes:None
126 schema:familyName Sudan
127 schema:givenName Madhu
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
129 rdf:type schema:Person
130 grid-institutes:None schema:alternateName Microsoft Research, Cambridge, MA, USA
131 schema:name Microsoft Research, Cambridge, MA, USA
132 rdf:type schema:Organization
133 grid-institutes:grid.116068.8 schema:alternateName MIT, Cambridge, MA, USA
134 schema:name MIT, Cambridge, MA, USA
135 rdf:type schema:Organization
 




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


...