Explicit subspace designs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2014-10-22

AUTHORS

Venkatesan Guruswami, Swastik Kopparty

ABSTRACT

A subspace design is a collection {H1, H2, ...,HM} of subspaces 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}_q^m$$\end{document} with the property that no low-dimensional subspace W 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}_q^m$$\end{document} intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal rate list-decodable codes over constant-sized large alphabets and sub-logarithmic (and even smaller) list size. Subspace designs are the only non-explicit part of their construction. In this paper, we give explicit constructions of subspace designs with parameters close to the probabilistic construction, and this implies the first deterministic polynomial time construction of list-decodable codes achieving the above parameters.Our constructions of subspace designs are natural and easily described, and are based on univariate polynomials over finite fields. Curiously, the constructions are very closely related to certain good list-decodable codes (folded RS codes and univariate multiplicity codes). The proof of the subspace design property uses the polynomial method (with multiplicities): Given a target low-dimensional subspace W, we construct a nonzero low-degree polynomial PW that has several roots for each Hi that non-trivially intersects W. The construction of PW is based on the classical Wronskian determinant and the folded Wronskian determinant, the latter being a recently studied notion that we make explicit in this paper. Our analysis reveals some new phenomena about the zeroes of univariate polynomials, namely that polynomials with many structured roots or many high multiplicity roots tend to be linearly independent. More... »

PAGES

161-185

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00493-014-3169-1

DOI

http://dx.doi.org/10.1007/s00493-014-3169-1

DIMENSIONS

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


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": "Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.147455.6", 
          "name": [
            "Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA"
          ], 
          "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": "Departments of Mathematics & Computer Science, Rutgers University, New Brunswick, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Departments of Mathematics & Computer Science, Rutgers University, New Brunswick, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kopparty", 
        "givenName": "Swastik", 
        "id": "sg:person.014276170447.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01170848", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046983517", 
          "https://doi.org/10.1007/bf01170848"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2014-10-22", 
    "datePublishedReg": "2014-10-22", 
    "description": "A subspace design is a collection {H1, H2, ...,HM} of subspaces 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}_q^m$$\\end{document} with the property that no low-dimensional subspace W 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}_q^m$$\\end{document} intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal rate list-decodable codes over constant-sized large alphabets and sub-logarithmic (and even smaller) list size. Subspace designs are the only non-explicit part of their construction. In this paper, we give explicit constructions of subspace designs with parameters close to the probabilistic construction, and this implies the first deterministic polynomial time construction of list-decodable codes achieving the above parameters.Our constructions of subspace designs are natural and easily described, and are based on univariate polynomials over finite fields. Curiously, the constructions are very closely related to certain good list-decodable codes (folded RS codes and univariate multiplicity codes). The proof of the subspace design property uses the polynomial method (with multiplicities): Given a target low-dimensional subspace W, we construct a nonzero low-degree polynomial PW that has several roots for each Hi that non-trivially intersects W. The construction of PW is based on the classical Wronskian determinant and the folded Wronskian determinant, the latter being a recently studied notion that we make explicit in this paper. Our analysis reveals some new phenomena about the zeroes of univariate polynomials, namely that polynomials with many structured roots or many high multiplicity roots tend to be linearly independent.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00493-014-3169-1", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3659247", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3111086", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "36"
      }
    ], 
    "keywords": [
      "subspace designs", 
      "Wronskian determinant", 
      "list-decodable codes", 
      "univariate polynomials", 
      "subspace W", 
      "finite field", 
      "explicit construction", 
      "probabilistic construction", 
      "polynomial method", 
      "randomized construction", 
      "polynomials", 
      "subspace", 
      "polynomial time construction", 
      "deterministic polynomial time construction", 
      "large alphabets", 
      "time construction", 
      "new phenomenon", 
      "parameters", 
      "design properties", 
      "zeros", 
      "code", 
      "properties", 
      "Guruswami", 
      "construction", 
      "list size", 
      "field", 
      "proof", 
      "design", 
      "above parameters", 
      "alphabet", 
      "phenomenon", 
      "Xing", 
      "notion", 
      "paper", 
      "size", 
      "PW", 
      "roots", 
      "HM", 
      "analysis", 
      "H2", 
      "collection", 
      "part", 
      "H1", 
      "method", 
      "determinants", 
      "optimal rate list-decodable codes", 
      "structured roots"
    ], 
    "name": "Explicit subspace designs", 
    "pagination": "161-185", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1007420779"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00493-014-3169-1"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00493-014-3169-1", 
      "https://app.dimensions.ai/details/publication/pub.1007420779"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-06-01T22:12", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/article/article_639.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00493-014-3169-1"
  }
]
 

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/s00493-014-3169-1'

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/s00493-014-3169-1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-014-3169-1'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-014-3169-1'


 

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

123 TRIPLES      22 PREDICATES      73 URIs      64 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00493-014-3169-1 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nda33cf5268fd4fc4b1c6b13ec0f8a658
4 schema:citation sg:pub.10.1007/bf01170848
5 schema:datePublished 2014-10-22
6 schema:datePublishedReg 2014-10-22
7 schema:description A subspace design is a collection {H1, H2, ...,HM} of subspaces 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}_q^m$$\end{document} with the property that no low-dimensional subspace W 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}_q^m$$\end{document} intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal rate list-decodable codes over constant-sized large alphabets and sub-logarithmic (and even smaller) list size. Subspace designs are the only non-explicit part of their construction. In this paper, we give explicit constructions of subspace designs with parameters close to the probabilistic construction, and this implies the first deterministic polynomial time construction of list-decodable codes achieving the above parameters.Our constructions of subspace designs are natural and easily described, and are based on univariate polynomials over finite fields. Curiously, the constructions are very closely related to certain good list-decodable codes (folded RS codes and univariate multiplicity codes). The proof of the subspace design property uses the polynomial method (with multiplicities): Given a target low-dimensional subspace W, we construct a nonzero low-degree polynomial PW that has several roots for each Hi that non-trivially intersects W. The construction of PW is based on the classical Wronskian determinant and the folded Wronskian determinant, the latter being a recently studied notion that we make explicit in this paper. Our analysis reveals some new phenomena about the zeroes of univariate polynomials, namely that polynomials with many structured roots or many high multiplicity roots tend to be linearly independent.
8 schema:genre article
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N40a9e90282144d7f9eebb4d8400462b3
12 N7fbc5894d6984277864153a319368027
13 sg:journal.1136493
14 schema:keywords Guruswami
15 H1
16 H2
17 HM
18 PW
19 Wronskian determinant
20 Xing
21 above parameters
22 alphabet
23 analysis
24 code
25 collection
26 construction
27 design
28 design properties
29 determinants
30 deterministic polynomial time construction
31 explicit construction
32 field
33 finite field
34 large alphabets
35 list size
36 list-decodable codes
37 method
38 new phenomenon
39 notion
40 optimal rate list-decodable codes
41 paper
42 parameters
43 part
44 phenomenon
45 polynomial method
46 polynomial time construction
47 polynomials
48 probabilistic construction
49 proof
50 properties
51 randomized construction
52 roots
53 size
54 structured roots
55 subspace
56 subspace W
57 subspace designs
58 time construction
59 univariate polynomials
60 zeros
61 schema:name Explicit subspace designs
62 schema:pagination 161-185
63 schema:productId N83acec81a2a340a897f5c6385d2ddb5b
64 N97d7a82900604205ab70492ca41d8248
65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007420779
66 https://doi.org/10.1007/s00493-014-3169-1
67 schema:sdDatePublished 2022-06-01T22:12
68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
69 schema:sdPublisher N6fddf0e4caa1479682573462d03a2bf8
70 schema:url https://doi.org/10.1007/s00493-014-3169-1
71 sgo:license sg:explorer/license/
72 sgo:sdDataset articles
73 rdf:type schema:ScholarlyArticle
74 N40a9e90282144d7f9eebb4d8400462b3 schema:issueNumber 2
75 rdf:type schema:PublicationIssue
76 N619b35036175422d8dcd55edcba6d20b rdf:first sg:person.014276170447.16
77 rdf:rest rdf:nil
78 N6fddf0e4caa1479682573462d03a2bf8 schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 N7fbc5894d6984277864153a319368027 schema:volumeNumber 36
81 rdf:type schema:PublicationVolume
82 N83acec81a2a340a897f5c6385d2ddb5b schema:name dimensions_id
83 schema:value pub.1007420779
84 rdf:type schema:PropertyValue
85 N97d7a82900604205ab70492ca41d8248 schema:name doi
86 schema:value 10.1007/s00493-014-3169-1
87 rdf:type schema:PropertyValue
88 Nda33cf5268fd4fc4b1c6b13ec0f8a658 rdf:first sg:person.015711462165.98
89 rdf:rest N619b35036175422d8dcd55edcba6d20b
90 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
91 schema:name Mathematical Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
94 schema:name Pure Mathematics
95 rdf:type schema:DefinedTerm
96 sg:grant.3111086 http://pending.schema.org/fundedItem sg:pub.10.1007/s00493-014-3169-1
97 rdf:type schema:MonetaryGrant
98 sg:grant.3659247 http://pending.schema.org/fundedItem sg:pub.10.1007/s00493-014-3169-1
99 rdf:type schema:MonetaryGrant
100 sg:journal.1136493 schema:issn 0209-9683
101 1439-6912
102 schema:name Combinatorica
103 schema:publisher Springer Nature
104 rdf:type schema:Periodical
105 sg:person.014276170447.16 schema:affiliation grid-institutes:grid.430387.b
106 schema:familyName Kopparty
107 schema:givenName Swastik
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16
109 rdf:type schema:Person
110 sg:person.015711462165.98 schema:affiliation grid-institutes:grid.147455.6
111 schema:familyName Guruswami
112 schema:givenName Venkatesan
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015711462165.98
114 rdf:type schema:Person
115 sg:pub.10.1007/bf01170848 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046983517
116 https://doi.org/10.1007/bf01170848
117 rdf:type schema:CreativeWork
118 grid-institutes:grid.147455.6 schema:alternateName Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
119 schema:name Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
120 rdf:type schema:Organization
121 grid-institutes:grid.430387.b schema:alternateName Departments of Mathematics & Computer Science, Rutgers University, New Brunswick, NJ, USA
122 schema:name Departments of Mathematics & Computer Science, Rutgers University, New Brunswick, NJ, USA
123 rdf:type schema:Organization
 




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


...