The Library
Random permutations using switching networks
Tools
Tools
Tools
Czumaj, Artur (2015) Random permutations using switching networks. In: Forty-Seventh Annual ACM on Symposium on Theory of Computing, Portland, Oregon, 15-17 Jun 2015. Published in: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing pp. 703-712. ISBN 9781450335362. doi:10.1145/2746539.2746629
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1145/2746539.2746629
Abstract
We consider the problem of designing a simple, oblivious scheme to generate (almost) random permutations. We use the concept of switching networks and show that almost every switching network of logarithmic depth can be used to almost randomly permute any set of (1-ε) n elements with any ε > 0 (that is, gives an almost (1-ε) n$-wise independent permutation). Furthermore, we show that the result still holds for every switching network of logarithmic depth that has some special expansion properties, leading to an explicit construction of such networks. Our result can be also extended to an explicit construction of a switching network of depth O(log2n) and with O(n log n) switches that almost randomly permutes any set of n elements. We also discuss basic applications of these results in cryptography. Our results are obtained using a non-trivial coupling approach to study mixing times of Markov chains which allows us to reduce the problem to some random walk-like problem on expanders.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Journal or Publication Title: | Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing | ||||
| Publisher: | ACM | ||||
| ISBN: | 9781450335362 | ||||
| Book Title: | Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing - STOC '15 | ||||
| Official Date: | 14 June 2015 | ||||
| Dates: |
|
||||
| Page Range: | pp. 703-712 | ||||
| DOI: | 10.1145/2746539.2746629 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||
| Date of first compliant deposit: | 4 March 2016 | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | Forty-Seventh Annual ACM on Symposium on Theory of Computing | ||||
| Type of Event: | Other | ||||
| Location of Event: | Portland, Oregon | ||||
| Date(s) of Event: | 15-17 Jun 2015 | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
