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": [
      "construction", 
      "amount of attention", 
      "attention", 
      "recent years", 
      "years", 
      "cases", 
      "independent functions", 
      "family", 
      "size of family", 
      "consistent labeling", 
      "labeling", 
      "factors", 
      "independent permutations", 
      "permutations", 
      "amount", 
      "function", 
      "size", 
      "paper", 
      "new method", 
      "method", 
      "generator", 
      "fact", 
      "pseudorandom", 
      "log-space algorithm", 
      "undirected connectivity", 
      "connectivity", 
      "length", 
      "constant factor", 
      "distance", 
      "uniform", 
      "description", 
      "wise independent functions", 
      "such permutations", 
      "previous constructions", 
      "pseudorandom generators", 
      "space-bounded computation", 
      "computation", 
      "undirected graph", 
      "graph", 
      "such generators", 
      "Reingold\u2019s log-space algorithm", 
      "algorithm", 
      "optimal description length", 
      "description length", 
      "tuples", 
      "wise independent permutations"
    ], 
    "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-01-01T19:08", 
    "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_140.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.

138 TRIPLES      23 PREDICATES      72 URIs      65 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 Nac681e011ccd4ababe996ee5b028b256
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 N08941d439ac64b958f6863106109f49f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N52e2640797e04bf095a9a3f1e638edac
12 schema:keywords Reingold’s log-space algorithm
13 algorithm
14 amount
15 amount of attention
16 attention
17 cases
18 computation
19 connectivity
20 consistent labeling
21 constant factor
22 construction
23 description
24 description length
25 distance
26 fact
27 factors
28 family
29 function
30 generator
31 graph
32 independent functions
33 independent permutations
34 labeling
35 length
36 log-space algorithm
37 method
38 new method
39 optimal description length
40 paper
41 permutations
42 previous constructions
43 pseudorandom
44 pseudorandom generators
45 recent years
46 size
47 size of family
48 space-bounded computation
49 such generators
50 such permutations
51 tuples
52 undirected connectivity
53 undirected graph
54 uniform
55 wise independent functions
56 wise independent permutations
57 years
58 schema:name Derandomized Constructions of k-Wise (Almost) Independent Permutations
59 schema:pagination 354-365
60 schema:productId N24edfd8f81f648d592c341eecca3a0a9
61 Nfd89e74062064ee59012dbc7e1d853ec
62 schema:publisher N124f4935151344ff95dc49b1a38ca0d9
63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037921863
64 https://doi.org/10.1007/11538462_30
65 schema:sdDatePublished 2022-01-01T19:08
66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
67 schema:sdPublisher N94db60f2e80e4c74b5cc100fd4e8baeb
68 schema:url https://doi.org/10.1007/11538462_30
69 sgo:license sg:explorer/license/
70 sgo:sdDataset chapters
71 rdf:type schema:Chapter
72 N08941d439ac64b958f6863106109f49f rdf:first Nfd1334ba81134ff2a56e4fbf54d5ffa1
73 rdf:rest N167188c56e65471a92efaecc4c3c2ce8
74 N124f4935151344ff95dc49b1a38ca0d9 schema:name Springer Nature
75 rdf:type schema:Organisation
76 N167188c56e65471a92efaecc4c3c2ce8 rdf:first Ndc36e36d543b4085a5aca22645a7bc61
77 rdf:rest N189f7fd74a7b4a1e9417e40f71189181
78 N179682f165514f8db7941d9a89fe8e89 rdf:first sg:person.012547246003.78
79 rdf:rest rdf:nil
80 N189f7fd74a7b4a1e9417e40f71189181 rdf:first N9a3b78e43eaf40d48c8b43d32f4a9afa
81 rdf:rest N9b2320181f8a4c98a3cd7a894a3e9207
82 N1bba7fc1d65b41c28946c6fca77ce5e8 schema:familyName Trevisan
83 schema:givenName Luca
84 rdf:type schema:Person
85 N24edfd8f81f648d592c341eecca3a0a9 schema:name dimensions_id
86 schema:value pub.1037921863
87 rdf:type schema:PropertyValue
88 N30f7cd0c1d4e464680d679dd8bc4dcd4 rdf:first sg:person.07776170271.83
89 rdf:rest N179682f165514f8db7941d9a89fe8e89
90 N52e2640797e04bf095a9a3f1e638edac schema:isbn 978-3-540-28239-6
91 978-3-540-31874-3
92 schema:name Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
93 rdf:type schema:Book
94 N94db60f2e80e4c74b5cc100fd4e8baeb schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
96 N9a3b78e43eaf40d48c8b43d32f4a9afa schema:familyName Rolim
97 schema:givenName José D. P.
98 rdf:type schema:Person
99 N9b2320181f8a4c98a3cd7a894a3e9207 rdf:first N1bba7fc1d65b41c28946c6fca77ce5e8
100 rdf:rest rdf:nil
101 Nac681e011ccd4ababe996ee5b028b256 rdf:first sg:person.016351357345.24
102 rdf:rest N30f7cd0c1d4e464680d679dd8bc4dcd4
103 Ndc36e36d543b4085a5aca22645a7bc61 schema:familyName Jansen
104 schema:givenName Klaus
105 rdf:type schema:Person
106 Nfd1334ba81134ff2a56e4fbf54d5ffa1 schema:familyName Chekuri
107 schema:givenName Chandra
108 rdf:type schema:Person
109 Nfd89e74062064ee59012dbc7e1d853ec schema:name doi
110 schema:value 10.1007/11538462_30
111 rdf:type schema:PropertyValue
112 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
113 schema:name Psychology and Cognitive Sciences
114 rdf:type schema:DefinedTerm
115 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
116 schema:name Psychology
117 rdf:type schema:DefinedTerm
118 sg:person.012547246003.78 schema:affiliation grid-institutes:None
119 schema:familyName Reingold
120 schema:givenName Omer
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012547246003.78
122 rdf:type schema:Person
123 sg:person.016351357345.24 schema:affiliation grid-institutes:grid.12136.37
124 schema:familyName Kaplan
125 schema:givenName Eyal
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016351357345.24
127 rdf:type schema:Person
128 sg:person.07776170271.83 schema:affiliation grid-institutes:None
129 schema:familyName Naor
130 schema:givenName Moni
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
132 rdf:type schema:Person
133 grid-institutes:None schema:alternateName Department of Computer Science and Applied Math, Weizmann Institute of Science
134 schema:name Department of Computer Science and Applied Math, Weizmann Institute of Science
135 rdf:type schema:Organization
136 grid-institutes:grid.12136.37 schema:alternateName Tel-Aviv University
137 schema:name Tel-Aviv University
138 rdf:type schema:Organization
 




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


...