On Representations of Algebraic-Geometric Codes for List Decoding View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2000

AUTHORS

Venkatesan Guruswami , Madhu Sudan

ABSTRACT

We show that all algebraic-geometric codes possess a succinct representation that allows for the list decoding algorithms of [15, 7] to run in polynomial time. We do this by presenting a root-finding algorithm for univariate polynomials over function fields when their coefficients lie in finite-dimensional linear spaces, and proving that there is a polynomial size representation given which the root finding algorithm runs in polynomial time. More... »

PAGES

244-255

Book

TITLE

Algorithms - ESA 2000

ISBN

978-3-540-41004-1
978-3-540-45253-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45253-2_23

DOI

http://dx.doi.org/10.1007/3-540-45253-2_23

DIMENSIONS

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


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": "Laboratory for Computer Science, Massachusetts Institute of Technology, 02139, Cambridge, MA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Laboratory for Computer Science, Massachusetts Institute of Technology, 02139, Cambridge, MA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Guruswami", 
        "givenName": "Venkatesan", 
        "id": "sg:person.015711462165.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015711462165.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Laboratory for Computer Science, Massachusetts Institute of Technology, 02139, Cambridge, MA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Laboratory for Computer Science, Massachusetts Institute of Technology, 02139, Cambridge, MA"
          ], 
          "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": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "We show that all algebraic-geometric codes possess a succinct representation that allows for the list decoding algorithms of [15, 7] to run in polynomial time. We do this by presenting a root-finding algorithm for univariate polynomials over function fields when their coefficients lie in finite-dimensional linear spaces, and proving that there is a polynomial size representation given which the root finding algorithm runs in polynomial time.", 
    "editor": [
      {
        "familyName": "Paterson", 
        "givenName": "Mike S.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45253-2_23", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-41004-1", 
        "978-3-540-45253-9"
      ], 
      "name": "Algorithms - ESA 2000", 
      "type": "Book"
    }, 
    "keywords": [
      "algebraic-geometric codes", 
      "finite-dimensional linear space", 
      "root-finding algorithm", 
      "polynomial time", 
      "polynomial size representation", 
      "linear space", 
      "function fields", 
      "univariate polynomials", 
      "algorithm runs", 
      "succinct representation", 
      "size representation", 
      "list decoding", 
      "algorithm", 
      "representation", 
      "polynomials", 
      "code", 
      "space", 
      "decoding", 
      "coefficient", 
      "field", 
      "time", 
      "run", 
      "list", 
      "roots"
    ], 
    "name": "On Representations of Algebraic-Geometric Codes for List Decoding", 
    "pagination": "244-255", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1053590153"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45253-2_23"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45253-2_23", 
      "https://app.dimensions.ai/details/publication/pub.1053590153"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:25", 
    "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_444.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45253-2_23"
  }
]
 

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/3-540-45253-2_23'

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/3-540-45253-2_23'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45253-2_23'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-45253-2_23'


 

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

91 TRIPLES      23 PREDICATES      50 URIs      43 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45253-2_23 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N77b8404a382a48a48fc274c708fa001f
4 schema:datePublished 2000
5 schema:datePublishedReg 2000-01-01
6 schema:description We show that all algebraic-geometric codes possess a succinct representation that allows for the list decoding algorithms of [15, 7] to run in polynomial time. We do this by presenting a root-finding algorithm for univariate polynomials over function fields when their coefficients lie in finite-dimensional linear spaces, and proving that there is a polynomial size representation given which the root finding algorithm runs in polynomial time.
7 schema:editor N3b2d3c58418746968bf5f34a4f14c635
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N262349283f994e5286923dce11a73166
12 schema:keywords algebraic-geometric codes
13 algorithm
14 algorithm runs
15 code
16 coefficient
17 decoding
18 field
19 finite-dimensional linear space
20 function fields
21 linear space
22 list
23 list decoding
24 polynomial size representation
25 polynomial time
26 polynomials
27 representation
28 root-finding algorithm
29 roots
30 run
31 size representation
32 space
33 succinct representation
34 time
35 univariate polynomials
36 schema:name On Representations of Algebraic-Geometric Codes for List Decoding
37 schema:pagination 244-255
38 schema:productId N02d90670239647eea5561950286b2ee6
39 N711267e1d47d4391ab1cf9d0c41277cf
40 schema:publisher Ne14064391b2f4a91ae9ed3de668a6b2f
41 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053590153
42 https://doi.org/10.1007/3-540-45253-2_23
43 schema:sdDatePublished 2022-01-01T19:25
44 schema:sdLicense https://scigraph.springernature.com/explorer/license/
45 schema:sdPublisher N1d6607765eeb4536902b0ff170e35f14
46 schema:url https://doi.org/10.1007/3-540-45253-2_23
47 sgo:license sg:explorer/license/
48 sgo:sdDataset chapters
49 rdf:type schema:Chapter
50 N02d90670239647eea5561950286b2ee6 schema:name doi
51 schema:value 10.1007/3-540-45253-2_23
52 rdf:type schema:PropertyValue
53 N1d6607765eeb4536902b0ff170e35f14 schema:name Springer Nature - SN SciGraph project
54 rdf:type schema:Organization
55 N262349283f994e5286923dce11a73166 schema:isbn 978-3-540-41004-1
56 978-3-540-45253-9
57 schema:name Algorithms - ESA 2000
58 rdf:type schema:Book
59 N30b64df8224d40babc24eb5b366f73d3 rdf:first sg:person.014663420265.17
60 rdf:rest rdf:nil
61 N3b2d3c58418746968bf5f34a4f14c635 rdf:first N6ac636a0c1694030b9ec57105766275d
62 rdf:rest rdf:nil
63 N6ac636a0c1694030b9ec57105766275d schema:familyName Paterson
64 schema:givenName Mike S.
65 rdf:type schema:Person
66 N711267e1d47d4391ab1cf9d0c41277cf schema:name dimensions_id
67 schema:value pub.1053590153
68 rdf:type schema:PropertyValue
69 N77b8404a382a48a48fc274c708fa001f rdf:first sg:person.015711462165.98
70 rdf:rest N30b64df8224d40babc24eb5b366f73d3
71 Ne14064391b2f4a91ae9ed3de668a6b2f schema:name Springer Nature
72 rdf:type schema:Organisation
73 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
74 schema:name Mathematical Sciences
75 rdf:type schema:DefinedTerm
76 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
77 schema:name Pure Mathematics
78 rdf:type schema:DefinedTerm
79 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.116068.8
80 schema:familyName Sudan
81 schema:givenName Madhu
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
83 rdf:type schema:Person
84 sg:person.015711462165.98 schema:affiliation grid-institutes:grid.116068.8
85 schema:familyName Guruswami
86 schema:givenName Venkatesan
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015711462165.98
88 rdf:type schema:Person
89 grid-institutes:grid.116068.8 schema:alternateName Laboratory for Computer Science, Massachusetts Institute of Technology, 02139, Cambridge, MA
90 schema:name Laboratory for Computer Science, Massachusetts Institute of Technology, 02139, Cambridge, MA
91 rdf:type schema:Organization
 




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


...