Derandomized Constructions of k-Wise (Almost) Independent Permutations View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2005

AUTHORS

Eyal Kaplan , Moni Naor , Omer Reingold

ABSTRACT

Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal. This paper gives a new method for reducing the size of families given by previous constructions. Our method relies on pseudorandom generators for space-bounded computations. In fact, all we need is a generator, that produces “pseudorandom walks” on undirected graphs with a consistent labelling. One such generator is implied by Reingold’s log-space algorithm for undirected connectivity [21,22]. We obtain families of k-wise almost independent permutations, with an optimal description length, up to a constant factor. More precisely, if the distance from uniform for any k tuple should be at most δ, then the size of the description of a permutation in the family is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(kn +\log \frac 1 {\delta})$\end{document}. More... »

PAGES

354-365

Book

TITLE

Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-540-28239-6
978-3-540-31874-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11538462_30

DOI

http://dx.doi.org/10.1007/11538462_30

DIMENSIONS

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


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/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/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Tel-Aviv University", 
          "id": "http://www.grid.ac/institutes/grid.12136.37", 
          "name": [
            "Tel-Aviv University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kaplan", 
        "givenName": "Eyal", 
        "id": "sg:person.016351357345.24", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016351357345.24"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Applied Math, Weizmann Institute of Science", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science and Applied Math, Weizmann Institute of Science"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Naor", 
        "givenName": "Moni", 
        "id": "sg:person.07776170271.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Applied Math, Weizmann Institute of Science", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science and Applied Math, Weizmann Institute of Science"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Reingold", 
        "givenName": "Omer", 
        "id": "sg:person.012547246003.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012547246003.78"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal. This paper gives a new method for reducing the size of families given by previous constructions. Our method relies on pseudorandom generators for space-bounded computations. In fact, all we need is a generator, that produces \u201cpseudorandom walks\u201d on undirected graphs with a consistent labelling. One such generator is implied by Reingold\u2019s log-space algorithm for undirected connectivity\u00a0[21,22]. We obtain families of k-wise almost independent permutations, with an optimal description length, up to a constant factor. More precisely, if the distance from uniform for any k tuple should be at most \u03b4, then the size of the description of a permutation in the family is \\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}$O(kn +\\log \\frac 1 {\\delta})$\\end{document}.", 
    "editor": [
      {
        "familyName": "Chekuri", 
        "givenName": "Chandra", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }, 
      {
        "familyName": "Trevisan", 
        "givenName": "Luca", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11538462_30", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-28239-6", 
        "978-3-540-31874-3"
      ], 
      "name": "Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "wise independent functions", 
      "wise independent permutations", 
      "size of family", 
      "log-space algorithm", 
      "amount of attention", 
      "family", 
      "undirected connectivity", 
      "construction", 
      "recent years", 
      "attention", 
      "space-bounded computation", 
      "independent permutations", 
      "fact", 
      "paper", 
      "years", 
      "factors", 
      "cases", 
      "description", 
      "connectivity", 
      "uniform", 
      "such permutations", 
      "distance", 
      "method", 
      "constant factor", 
      "permutations", 
      "size", 
      "amount", 
      "previous constructions", 
      "function", 
      "labeling", 
      "independent functions", 
      "consistent labeling", 
      "new method", 
      "generator", 
      "length", 
      "such generators", 
      "pseudorandom generators", 
      "graph", 
      "undirected graph", 
      "description length", 
      "pseudorandom", 
      "computation", 
      "algorithm", 
      "tuples"
    ], 
    "name": "Derandomized Constructions of k-Wise (Almost) Independent Permutations", 
    "pagination": "354-365", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037921863"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11538462_30"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11538462_30", 
      "https://app.dimensions.ai/details/publication/pub.1037921863"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:49", 
    "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_88.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11538462_30"
  }
]
 

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/11538462_30'

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/11538462_30'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11538462_30'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11538462_30'


 

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

136 TRIPLES      23 PREDICATES      70 URIs      63 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11538462_30 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author N4b05addc6e084893aa86b2107eab043b
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal. This paper gives a new method for reducing the size of families given by previous constructions. Our method relies on pseudorandom generators for space-bounded computations. In fact, all we need is a generator, that produces “pseudorandom walks” on undirected graphs with a consistent labelling. One such generator is implied by Reingold’s log-space algorithm for undirected connectivity [21,22]. We obtain families of k-wise almost independent permutations, with an optimal description length, up to a constant factor. More precisely, if the distance from uniform for any k tuple should be at most δ, then the size of the description of a permutation in the family is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(kn +\log \frac 1 {\delta})$\end{document}.
7 schema:editor N2fad642761f44d0184e37bcd6edcfe89
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N2583634f41b54535a08f39eb7a5c1dce
12 schema:keywords algorithm
13 amount
14 amount of attention
15 attention
16 cases
17 computation
18 connectivity
19 consistent labeling
20 constant factor
21 construction
22 description
23 description length
24 distance
25 fact
26 factors
27 family
28 function
29 generator
30 graph
31 independent functions
32 independent permutations
33 labeling
34 length
35 log-space algorithm
36 method
37 new method
38 paper
39 permutations
40 previous constructions
41 pseudorandom
42 pseudorandom generators
43 recent years
44 size
45 size of family
46 space-bounded computation
47 such generators
48 such permutations
49 tuples
50 undirected connectivity
51 undirected graph
52 uniform
53 wise independent functions
54 wise independent permutations
55 years
56 schema:name Derandomized Constructions of k-Wise (Almost) Independent Permutations
57 schema:pagination 354-365
58 schema:productId Nd0a17203aae443caafe2df42112b41c3
59 Ne53105320ca941678040da3e5ff5bb72
60 schema:publisher N71c0ba225b9f42b5851e347e40cb7437
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037921863
62 https://doi.org/10.1007/11538462_30
63 schema:sdDatePublished 2022-05-20T07:49
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher N758dbd7e16594457b262d670eb746823
66 schema:url https://doi.org/10.1007/11538462_30
67 sgo:license sg:explorer/license/
68 sgo:sdDataset chapters
69 rdf:type schema:Chapter
70 N208bd3b08898474490b8353a8d8fc1ba rdf:first Nc667284ca6574bfd8ac7207aa7708a0e
71 rdf:rest N8396f1af58cf4940b8336d1c6d3ec3f9
72 N2583634f41b54535a08f39eb7a5c1dce schema:isbn 978-3-540-28239-6
73 978-3-540-31874-3
74 schema:name Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
75 rdf:type schema:Book
76 N2fad642761f44d0184e37bcd6edcfe89 rdf:first N521453f087fa4fb4a6c642b5067d7935
77 rdf:rest N208bd3b08898474490b8353a8d8fc1ba
78 N4b05addc6e084893aa86b2107eab043b rdf:first sg:person.016351357345.24
79 rdf:rest N6e7fbc13c42e41c696e345193f761557
80 N521453f087fa4fb4a6c642b5067d7935 schema:familyName Chekuri
81 schema:givenName Chandra
82 rdf:type schema:Person
83 N6e7fbc13c42e41c696e345193f761557 rdf:first sg:person.07776170271.83
84 rdf:rest N8515d4a3ff3c49a6aec1351785296115
85 N71c0ba225b9f42b5851e347e40cb7437 schema:name Springer Nature
86 rdf:type schema:Organisation
87 N758dbd7e16594457b262d670eb746823 schema:name Springer Nature - SN SciGraph project
88 rdf:type schema:Organization
89 N8396f1af58cf4940b8336d1c6d3ec3f9 rdf:first Nfdae9034bdcf4902a7fe72ab9f6f652c
90 rdf:rest Ncc700f7927684de8b897f826da48813b
91 N8515d4a3ff3c49a6aec1351785296115 rdf:first sg:person.012547246003.78
92 rdf:rest rdf:nil
93 Na2da0ae43bbe464b8d55b8fcdb908990 schema:familyName Trevisan
94 schema:givenName Luca
95 rdf:type schema:Person
96 Nc667284ca6574bfd8ac7207aa7708a0e schema:familyName Jansen
97 schema:givenName Klaus
98 rdf:type schema:Person
99 Ncc700f7927684de8b897f826da48813b rdf:first Na2da0ae43bbe464b8d55b8fcdb908990
100 rdf:rest rdf:nil
101 Nd0a17203aae443caafe2df42112b41c3 schema:name doi
102 schema:value 10.1007/11538462_30
103 rdf:type schema:PropertyValue
104 Ne53105320ca941678040da3e5ff5bb72 schema:name dimensions_id
105 schema:value pub.1037921863
106 rdf:type schema:PropertyValue
107 Nfdae9034bdcf4902a7fe72ab9f6f652c schema:familyName Rolim
108 schema:givenName José D. P.
109 rdf:type schema:Person
110 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
111 schema:name Psychology and Cognitive Sciences
112 rdf:type schema:DefinedTerm
113 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
114 schema:name Psychology
115 rdf:type schema:DefinedTerm
116 sg:person.012547246003.78 schema:affiliation grid-institutes:None
117 schema:familyName Reingold
118 schema:givenName Omer
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012547246003.78
120 rdf:type schema:Person
121 sg:person.016351357345.24 schema:affiliation grid-institutes:grid.12136.37
122 schema:familyName Kaplan
123 schema:givenName Eyal
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016351357345.24
125 rdf:type schema:Person
126 sg:person.07776170271.83 schema:affiliation grid-institutes:None
127 schema:familyName Naor
128 schema:givenName Moni
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
130 rdf:type schema:Person
131 grid-institutes:None schema:alternateName Department of Computer Science and Applied Math, Weizmann Institute of Science
132 schema:name Department of Computer Science and Applied Math, Weizmann Institute of Science
133 rdf:type schema:Organization
134 grid-institutes:grid.12136.37 schema:alternateName Tel-Aviv University
135 schema:name Tel-Aviv University
136 rdf:type schema:Organization
 




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


...