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

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.

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
 




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


...