Gelman, Efraim ;
TaShma, Amnon
The Benes Network is q*(q1)/2nAlmost qsetwise Independent
Abstract
A switching network of depth d is a layered graph with d layers and n vertices in each layer. The edges of the switching network do not cross between layers and in each layer the edges form a partial matching. A switching network defines a stochastic process over Sn that starts with the identity permutation and goes through the layers of the network from first to last, where for each layer and each pair (i,j) in the partial matching of the layer, it applies the transposition (i j) with probability half. A switching network is good if the final distribution is close to the uniform distribution over S_n.
A switching network is epsilonalmost qpermutationwise independent if its action on any ordered set of size q is almost uniform, and is epsilonalmost qsetwise independent if its action on any set of size q is almost uniform. Mixing of switching networks (even for qpermutationwise and qsetwise independence) has found several applications, mostly in cryptography. Some applications further require some additional properties from the network, e.g., the existence of an algorithm that given a permutation can set the switches such that the network generates the given permutation, a property that the Benes network has.
Morris, Rogaway and Stegers showed the Thorp shuffle (which corresponds to applying two or more butterflies one after the other) is qpermutationwise independent, for q=n^gamma for gamma that depends on the number of sequential applications of the butterfly network. The techniques applied by Morris et al. do not seem to apply for the Benes network.
In this work we show the Benes network is almost qsetwise independent for q up to about sqrt(n). Our technique is simple and completely new, and we believe carries hope for getting even better results in the future.
BibTeX  Entry
@InProceedings{gelman_et_al:LIPIcs:2014:4853,
author = {Efraim Gelman and Amnon TaShma},
title = {{The Benes Network is q*(q1)/2nAlmost qsetwise Independent}},
booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
pages = {327338},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897774},
ISSN = {18688969},
year = {2014},
volume = {29},
editor = {Venkatesh Raman and S. P. Suresh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4853},
URN = {urn:nbn:de:0030drops48538},
doi = {10.4230/LIPIcs.FSTTCS.2014.327},
annote = {Keywords: switching network, mixing, Benes}
}
2014
Keywords: 

switching network, mixing, Benes 
Seminar: 

34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Issue date: 

2014 
Date of publication: 

2014 