Flight over Bristol

Bristol Algorithms Days 2010
Feasibility Workshop

15 - 16 February 2010

  •    •    •  

Generating Random Permutations in Networks

Artur Czumaj

A switching network may be used for generating random permutations. After setting the values of switches at random, the network performs a fixed permutation of the input data. If the switches are set at random, then in some sense the switching network performs a random permutation. Additionally, from the point of view of possible applications, it is reasonable to demand that the resulting probability distribution on the set of permutations is almost uniform.

We will present some constructions of switching networks with n inputs with a depth polynomial in log(n) which generate almost random permutations (the variation distance between the uniform distribution on the set of all permutations and the probability distribution defined by the network is o(1)).


  The University of Bristol   EPSRC