Sparse affine-invariant linear codes are locally testable View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2015-10-29

AUTHORS

Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan

ABSTRACT

We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field Fq\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}$$\end{document} and an extension field Fqn\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^n}}$$\end{document}, a property is a set of functions mapping Fqn\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^n}}$$\end{document} to Fq\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}$$\end{document}. The property is said to be affine-invariant if it is invariant under affine transformations of Fqn\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^n}}$$\end{document}, linear if it is an Fq\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}$$\end{document} -vector space, and sparse if its size is polynomial in the domain size. Our work completes a line of work initiated by Grigorescu et al. (2009) and followed by Kaufman & Lovett (2011). The latter showed such a result for the case when q was prime. Extending to non-prime cases turns out to be non-trivial, and our proof involves some detours into additive combinatorics, as well as a new calculus for building property testers for affine-invariant linear properties. More... »

PAGES

37-77

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00037-015-0115-6

DOI

http://dx.doi.org/10.1007/s00037-015-0115-6

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1702", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Cognitive Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Technion, Haifa, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Department of Computer Science, Technion, Haifa, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ben-Sasson", 
        "givenName": "Eli", 
        "id": "sg:person.014331106007.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014331106007.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "DIMACS, Rutgers University, Piscataway, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.469777.c", 
          "name": [
            "School of Mathematics, Institute for Advanced Study, Princeton, NJ, USA", 
            "DIMACS, Rutgers University, Piscataway, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ron-Zewi", 
        "givenName": "Noga", 
        "id": "sg:person.013153216765.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013153216765.32"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Microsoft Research New England, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Microsoft Research New England, 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"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s00039-004-0451-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026674461", 
          "https://doi.org/10.1007/s00039-004-0451-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-22935-0_34", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049575323", 
          "https://doi.org/10.1007/978-3-642-22935-0_34"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-09519-5_73", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030416919", 
          "https://doi.org/10.1007/3-540-09519-5_73"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-22935-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010325477", 
          "https://doi.org/10.1007/978-3-642-22935-0"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2015-10-29", 
    "datePublishedReg": "2015-10-29", 
    "description": "We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field Fq\\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}$$\\end{document} and an extension field Fqn\\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^n}}$$\\end{document}, a property is a set of functions mapping Fqn\\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^n}}$$\\end{document} to Fq\\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}$$\\end{document}. The property is said to be affine-invariant if it is invariant under affine transformations of Fqn\\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^n}}$$\\end{document}, linear if it is an Fq\\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}$$\\end{document} -vector space, and sparse if its size is polynomial in the domain size. Our work completes a line of work initiated by Grigorescu et\u00a0al. (2009) and followed by Kaufman & Lovett (2011). The latter showed such a result for the case when q was prime. Extending to non-prime cases turns out to be non-trivial, and our proof involves some detours into additive combinatorics, as well as a new calculus for building property testers for affine-invariant linear properties.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00037-015-0115-6", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136224", 
        "issn": [
          "1016-3328", 
          "1420-8954"
        ], 
        "name": "computational complexity", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "26"
      }
    ], 
    "keywords": [
      "finite field", 
      "non-prime cases", 
      "arbitrary finite fields", 
      "linear properties", 
      "set of functions", 
      "additive combinatorics", 
      "property tester", 
      "extension field", 
      "domain size", 
      "linear codes", 
      "new calculus", 
      "properties", 
      "affine transformation", 
      "field", 
      "constant number", 
      "combinatorics", 
      "tester", 
      "line of work", 
      "calculus", 
      "size", 
      "work", 
      "space", 
      "proof", 
      "set", 
      "al", 
      "Lovett", 
      "function", 
      "code", 
      "transformation", 
      "results", 
      "cases", 
      "number", 
      "detour", 
      "ET", 
      "Kaufman", 
      "lines", 
      "queries", 
      "sparse affine-invariant linear properties", 
      "affine-invariant linear properties", 
      "Grigorescu et", 
      "Sparse affine-invariant linear codes", 
      "affine-invariant linear codes"
    ], 
    "name": "Sparse affine-invariant linear codes are locally testable", 
    "pagination": "37-77", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1021927816"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00037-015-0115-6"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00037-015-0115-6", 
      "https://app.dimensions.ai/details/publication/pub.1021927816"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-01-01T18:37", 
    "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/article/article_677.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00037-015-0115-6"
  }
]
 

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/s00037-015-0115-6'

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/s00037-015-0115-6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00037-015-0115-6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00037-015-0115-6'


 

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

149 TRIPLES      22 PREDICATES      74 URIs      59 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00037-015-0115-6 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 anzsrc-for:0802
4 anzsrc-for:17
5 anzsrc-for:1702
6 schema:author N355acc2e037c40fc905c3bdaf125b859
7 schema:citation sg:pub.10.1007/3-540-09519-5_73
8 sg:pub.10.1007/978-3-642-22935-0
9 sg:pub.10.1007/978-3-642-22935-0_34
10 sg:pub.10.1007/s00039-004-0451-1
11 schema:datePublished 2015-10-29
12 schema:datePublishedReg 2015-10-29
13 schema:description We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field Fq\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}$$\end{document} and an extension field Fqn\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^n}}$$\end{document}, a property is a set of functions mapping Fqn\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^n}}$$\end{document} to Fq\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}$$\end{document}. The property is said to be affine-invariant if it is invariant under affine transformations of Fqn\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^n}}$$\end{document}, linear if it is an Fq\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}$$\end{document} -vector space, and sparse if its size is polynomial in the domain size. Our work completes a line of work initiated by Grigorescu et al. (2009) and followed by Kaufman & Lovett (2011). The latter showed such a result for the case when q was prime. Extending to non-prime cases turns out to be non-trivial, and our proof involves some detours into additive combinatorics, as well as a new calculus for building property testers for affine-invariant linear properties.
14 schema:genre article
15 schema:inLanguage en
16 schema:isAccessibleForFree true
17 schema:isPartOf N7fa36d49aa41421487eacd41e1bf1f2b
18 N9d7d2124c9344d5d859a6c802f55eb08
19 sg:journal.1136224
20 schema:keywords ET
21 Grigorescu et
22 Kaufman
23 Lovett
24 Sparse affine-invariant linear codes
25 additive combinatorics
26 affine transformation
27 affine-invariant linear codes
28 affine-invariant linear properties
29 al
30 arbitrary finite fields
31 calculus
32 cases
33 code
34 combinatorics
35 constant number
36 detour
37 domain size
38 extension field
39 field
40 finite field
41 function
42 line of work
43 linear codes
44 linear properties
45 lines
46 new calculus
47 non-prime cases
48 number
49 proof
50 properties
51 property tester
52 queries
53 results
54 set
55 set of functions
56 size
57 space
58 sparse affine-invariant linear properties
59 tester
60 transformation
61 work
62 schema:name Sparse affine-invariant linear codes are locally testable
63 schema:pagination 37-77
64 schema:productId Nb12b77088e514afabc475cc99f0abad8
65 Ncc8e982747ed4e65af5e9e281198577d
66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021927816
67 https://doi.org/10.1007/s00037-015-0115-6
68 schema:sdDatePublished 2022-01-01T18:37
69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
70 schema:sdPublisher N79bbdeaf267a4126b5b1b75621b2352e
71 schema:url https://doi.org/10.1007/s00037-015-0115-6
72 sgo:license sg:explorer/license/
73 sgo:sdDataset articles
74 rdf:type schema:ScholarlyArticle
75 N355acc2e037c40fc905c3bdaf125b859 rdf:first sg:person.014331106007.34
76 rdf:rest N8c6c369550a44cafa42cf881b67c5278
77 N79bbdeaf267a4126b5b1b75621b2352e schema:name Springer Nature - SN SciGraph project
78 rdf:type schema:Organization
79 N7fa36d49aa41421487eacd41e1bf1f2b schema:issueNumber 1
80 rdf:type schema:PublicationIssue
81 N8c6c369550a44cafa42cf881b67c5278 rdf:first sg:person.013153216765.32
82 rdf:rest Ndf56cf60308040d2acc92435a23fea91
83 N9d7d2124c9344d5d859a6c802f55eb08 schema:volumeNumber 26
84 rdf:type schema:PublicationVolume
85 Nb12b77088e514afabc475cc99f0abad8 schema:name doi
86 schema:value 10.1007/s00037-015-0115-6
87 rdf:type schema:PropertyValue
88 Ncc8e982747ed4e65af5e9e281198577d schema:name dimensions_id
89 schema:value pub.1021927816
90 rdf:type schema:PropertyValue
91 Ndf56cf60308040d2acc92435a23fea91 rdf:first sg:person.014663420265.17
92 rdf:rest rdf:nil
93 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
94 schema:name Information and Computing Sciences
95 rdf:type schema:DefinedTerm
96 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
97 schema:name Artificial Intelligence and Image Processing
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
100 schema:name Computation Theory and Mathematics
101 rdf:type schema:DefinedTerm
102 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
103 schema:name Psychology and Cognitive Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:1702 schema:inDefinedTermSet anzsrc-for:
106 schema:name Cognitive Sciences
107 rdf:type schema:DefinedTerm
108 sg:journal.1136224 schema:issn 1016-3328
109 1420-8954
110 schema:name computational complexity
111 schema:publisher Springer Nature
112 rdf:type schema:Periodical
113 sg:person.013153216765.32 schema:affiliation grid-institutes:grid.469777.c
114 schema:familyName Ron-Zewi
115 schema:givenName Noga
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013153216765.32
117 rdf:type schema:Person
118 sg:person.014331106007.34 schema:affiliation grid-institutes:grid.6451.6
119 schema:familyName Ben-Sasson
120 schema:givenName Eli
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014331106007.34
122 rdf:type schema:Person
123 sg:person.014663420265.17 schema:affiliation grid-institutes:None
124 schema:familyName Sudan
125 schema:givenName Madhu
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
127 rdf:type schema:Person
128 sg:pub.10.1007/3-540-09519-5_73 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030416919
129 https://doi.org/10.1007/3-540-09519-5_73
130 rdf:type schema:CreativeWork
131 sg:pub.10.1007/978-3-642-22935-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010325477
132 https://doi.org/10.1007/978-3-642-22935-0
133 rdf:type schema:CreativeWork
134 sg:pub.10.1007/978-3-642-22935-0_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049575323
135 https://doi.org/10.1007/978-3-642-22935-0_34
136 rdf:type schema:CreativeWork
137 sg:pub.10.1007/s00039-004-0451-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026674461
138 https://doi.org/10.1007/s00039-004-0451-1
139 rdf:type schema:CreativeWork
140 grid-institutes:None schema:alternateName Microsoft Research New England, Cambridge, MA, USA
141 schema:name Microsoft Research New England, Cambridge, MA, USA
142 rdf:type schema:Organization
143 grid-institutes:grid.469777.c schema:alternateName DIMACS, Rutgers University, Piscataway, NJ, USA
144 schema:name DIMACS, Rutgers University, Piscataway, NJ, USA
145 School of Mathematics, Institute for Advanced Study, Princeton, NJ, USA
146 rdf:type schema:Organization
147 grid-institutes:grid.6451.6 schema:alternateName Department of Computer Science, Technion, Haifa, Israel
148 schema:name Department of Computer Science, Technion, Haifa, Israel
149 rdf:type schema:Organization
 




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


...