Distilling common randomness from bipartite quantum states
Igor Devetak, Andreas Winter
ISIT 2003
A tournament is a digraph in which every pair of vertices is connected by exactly one arc. The score list of a tournament is the sorted list of the out-degrees of its vertices. Given a nondecreasing sequence of nonnegative integers, is it the score list of some tournament? There is a simple test for answering this question. There is also a simple sequential algorithm for constructing a tournament with a given score list. However, this algorithm has a greedy nature, and seems hard to parallelize. We present a simple parallel algorithm for the construction problem. Our algorithm runs in time O(log n) and uses O(n2/log n) processors on a CREW PRAM, where n is the number of vertices. Since the size of the output is Θ(n2), our algorithm achieves optimal speedup. The tournament constructed has the property that it is the closest possible to a transitive tournament in a precise sense. © 1990.
Igor Devetak, Andreas Winter
ISIT 2003
M.B. Small, R.M. Potemski
Proceedings of SPIE 1989
Amir Ali Ahmadi, Raphaël M. Jungers, et al.
SICON
George Markowsky
J. Math. Anal. Appl.