Sample spaces with small bias on neighborhoods and error-correcting communication protocols View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1997

AUTHORS

Michael Saks , Shiyu Zhou

ABSTRACT

We give a deterministic algorithm which, on input an integer n, collection f of subsets of {1,2,⋯, n} and ∈ ∃ (0,1) runs in time polynomial in n‖f‖/∈ and produces a ±1-matrix M with n columns and m=O(log ‖f‖/∈2) rows with the following property: for any subset F ∃ f, the fraction of 1's in the n-vector obtained by coordinate-wise multiplication of the column vectors indexed by F is between (1−∈)/2 and (1+∈)/2. In the case that f is the set of all subsets of size at most k, k constant, this gives a polynomial time construction for a k-wise ∈-biased sample space of size O(log n/∈2), as compared to the best previous constructions of [NN90] and [AGHP91] which were, respectively, O(log n/∈4) and O((log n)2/∈2). The number of rows in the construction matches the upper bound given by the probabilistic existence argument. Such constructions are of interest for derandomizing algorithms. As an application, we present a family of essentially optimal deterministic communication protocols for the problem of checking the consistency of two files. More... »

PAGES

95-109

Book

TITLE

Randomization and Approximation Techniques in Computer Science

ISBN

978-3-540-63248-1
978-3-540-69247-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-63248-4_9

DOI

http://dx.doi.org/10.1007/3-540-63248-4_9

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "Michael", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Bell Laboratories, 700 Mountain Ave., 07974, Murray Hill, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.469490.6", 
          "name": [
            "Bell Laboratories, 700 Mountain Ave., 07974, Murray Hill, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhou", 
        "givenName": "Shiyu", 
        "id": "sg:person.015424351665.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015424351665.83"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1997", 
    "datePublishedReg": "1997-01-01", 
    "description": "We give a deterministic algorithm which, on input an integer n, collection f of subsets of {1,2,\u22ef, n} and \u2208 \u2203 (0,1) runs in time polynomial in n\u2016f\u2016/\u2208 and produces a \u00b11-matrix M with n columns and m=O(log \u2016f\u2016/\u22082) rows with the following property: for any subset F \u2203 f, the fraction of 1's in the n-vector obtained by coordinate-wise multiplication of the column vectors indexed by F is between (1\u2212\u2208)/2 and (1+\u2208)/2. In the case that f is the set of all subsets of size at most k, k constant, this gives a polynomial time construction for a k-wise \u2208-biased sample space of size O(log n/\u22082), as compared to the best previous constructions of [NN90] and [AGHP91] which were, respectively, O(log n/\u22084) and O((log n)2/\u22082). The number of rows in the construction matches the upper bound given by the probabilistic existence argument. Such constructions are of interest for derandomizing algorithms. As an application, we present a family of essentially optimal deterministic communication protocols for the problem of checking the consistency of two files.", 
    "editor": [
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-63248-4_9", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-63248-1", 
        "978-3-540-69247-8"
      ], 
      "name": "Randomization and Approximation Techniques in Computer Science", 
      "type": "Book"
    }, 
    "keywords": [
      "sample space", 
      "deterministic communication protocol", 
      "matrix M", 
      "existence arguments", 
      "n-vector", 
      "subset of size", 
      "deterministic algorithm", 
      "best previous constructions", 
      "time polynomial", 
      "column vectors", 
      "subset F", 
      "number of rows", 
      "polynomial time construction", 
      "integer n", 
      "previous constructions", 
      "collection F", 
      "small bias", 
      "time construction", 
      "communication protocols", 
      "algorithm", 
      "space", 
      "such constructions", 
      "K constants", 
      "polynomials", 
      "construction", 
      "problem", 
      "multiplication", 
      "neighborhood", 
      "set", 
      "vector", 
      "subset", 
      "properties", 
      "applications", 
      "input", 
      "constants", 
      "size", 
      "number", 
      "argument", 
      "rows", 
      "cases", 
      "consistency", 
      "interest", 
      "bias", 
      "family", 
      "protocol", 
      "fraction", 
      "files", 
      "column"
    ], 
    "name": "Sample spaces with small bias on neighborhoods and error-correcting communication protocols", 
    "pagination": "95-109", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048022710"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-63248-4_9"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-63248-4_9", 
      "https://app.dimensions.ai/details/publication/pub.1048022710"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:14", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_341.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-63248-4_9"
  }
]
 

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-63248-4_9'

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-63248-4_9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-63248-4_9'

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-63248-4_9'


 

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

117 TRIPLES      22 PREDICATES      73 URIs      66 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-63248-4_9 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Na4cd9dd4387f4205a798e27bdf00c6c9
4 schema:datePublished 1997
5 schema:datePublishedReg 1997-01-01
6 schema:description We give a deterministic algorithm which, on input an integer n, collection f of subsets of {1,2,⋯, n} and ∈ ∃ (0,1) runs in time polynomial in n‖f‖/∈ and produces a ±1-matrix M with n columns and m=O(log ‖f‖/∈2) rows with the following property: for any subset F ∃ f, the fraction of 1's in the n-vector obtained by coordinate-wise multiplication of the column vectors indexed by F is between (1−∈)/2 and (1+∈)/2. In the case that f is the set of all subsets of size at most k, k constant, this gives a polynomial time construction for a k-wise ∈-biased sample space of size O(log n/∈2), as compared to the best previous constructions of [NN90] and [AGHP91] which were, respectively, O(log n/∈4) and O((log n)2/∈2). The number of rows in the construction matches the upper bound given by the probabilistic existence argument. Such constructions are of interest for derandomizing algorithms. As an application, we present a family of essentially optimal deterministic communication protocols for the problem of checking the consistency of two files.
7 schema:editor Ne03ef27a59964323ac56f9dac3fb843f
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N4c28226fb33745cb96a42bc92dc81462
11 schema:keywords K constants
12 algorithm
13 applications
14 argument
15 best previous constructions
16 bias
17 cases
18 collection F
19 column
20 column vectors
21 communication protocols
22 consistency
23 constants
24 construction
25 deterministic algorithm
26 deterministic communication protocol
27 existence arguments
28 family
29 files
30 fraction
31 input
32 integer n
33 interest
34 matrix M
35 multiplication
36 n-vector
37 neighborhood
38 number
39 number of rows
40 polynomial time construction
41 polynomials
42 previous constructions
43 problem
44 properties
45 protocol
46 rows
47 sample space
48 set
49 size
50 small bias
51 space
52 subset
53 subset F
54 subset of size
55 such constructions
56 time construction
57 time polynomial
58 vector
59 schema:name Sample spaces with small bias on neighborhoods and error-correcting communication protocols
60 schema:pagination 95-109
61 schema:productId N42da7e14b41b45e29468f52191a5249f
62 Nb2db077db29b424ea6e14b80ead22629
63 schema:publisher N41eec51557114a5b91fc9d61fee7676b
64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048022710
65 https://doi.org/10.1007/3-540-63248-4_9
66 schema:sdDatePublished 2022-09-02T16:14
67 schema:sdLicense https://scigraph.springernature.com/explorer/license/
68 schema:sdPublisher Nd8b79ff1f25743d78c081d3a3a5d0de6
69 schema:url https://doi.org/10.1007/3-540-63248-4_9
70 sgo:license sg:explorer/license/
71 sgo:sdDataset chapters
72 rdf:type schema:Chapter
73 N41eec51557114a5b91fc9d61fee7676b schema:name Springer Nature
74 rdf:type schema:Organisation
75 N42da7e14b41b45e29468f52191a5249f schema:name doi
76 schema:value 10.1007/3-540-63248-4_9
77 rdf:type schema:PropertyValue
78 N4c28226fb33745cb96a42bc92dc81462 schema:isbn 978-3-540-63248-1
79 978-3-540-69247-8
80 schema:name Randomization and Approximation Techniques in Computer Science
81 rdf:type schema:Book
82 Na4cd9dd4387f4205a798e27bdf00c6c9 rdf:first sg:person.011520224512.05
83 rdf:rest Nfb2d5762e2e942f2af0c968771729ec9
84 Nb2db077db29b424ea6e14b80ead22629 schema:name dimensions_id
85 schema:value pub.1048022710
86 rdf:type schema:PropertyValue
87 Nbe4dfc6eb9434954ba90226971d184bc schema:familyName Rolim
88 schema:givenName José
89 rdf:type schema:Person
90 Nd8b79ff1f25743d78c081d3a3a5d0de6 schema:name Springer Nature - SN SciGraph project
91 rdf:type schema:Organization
92 Ne03ef27a59964323ac56f9dac3fb843f rdf:first Nbe4dfc6eb9434954ba90226971d184bc
93 rdf:rest rdf:nil
94 Nfb2d5762e2e942f2af0c968771729ec9 rdf:first sg:person.015424351665.83
95 rdf:rest rdf:nil
96 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
97 schema:name Information and Computing Sciences
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 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
103 schema:familyName Saks
104 schema:givenName Michael
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
106 rdf:type schema:Person
107 sg:person.015424351665.83 schema:affiliation grid-institutes:grid.469490.6
108 schema:familyName Zhou
109 schema:givenName Shiyu
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015424351665.83
111 rdf:type schema:Person
112 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA
113 schema:name Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA
114 rdf:type schema:Organization
115 grid-institutes:grid.469490.6 schema:alternateName Bell Laboratories, 700 Mountain Ave., 07974, Murray Hill, NJ, USA
116 schema:name Bell Laboratories, 700 Mountain Ave., 07974, Murray Hill, NJ, USA
117 rdf:type schema:Organization
 




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


...