TY - GEN
T1 - Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions
AU - Alon, Noga
AU - Lovett, Shachar
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2012
Y1 - 2012
N2 - A family of permutations in S n is k-wise independent if a uniform permutation chosen from the family maps any distinct k elements to any distinct k elements equally likely. Efficient constructions of k-wise independent permutations are known for k = 2 and k = 3, but are unknown for k ≥ 4. In fact, it is known that there are no nontrivial subgroups of S n for n ≥ 25 which are 4-wise independent. Faced with this adversity, research has turned towards constructing almost k-wise independent families, where small errors are allowed. Optimal constructions of almost k-wise independent families of permutations were achieved by several authors. Our first result is that any such family with small enough error is statistically close to a distribution which is perfectly k-wise independent. This allows for a simplified analysis of algorithms: an algorithm which uses randomized permutations can be analyzed assuming perfect k-wise independence, and then applied to an almost k-wise independent family. In particular, it allows for an oblivious derandomization of two-sided randomized algorithms which work correctly given any k-wise independent distribution of permutations. Another model is that of weighted families of permutations, or equivalently distributions of small support. We establish two results in this model. First, we show that a small random set of n O(k) permutations w.h.p supports a k-wise independent distribution. We then derandomize this by showing that any almost 2k-wise independent family supports a k-wise independent distribution. This allows for oblivious derandomization of algorithms for search problems which work correctly given perfect k-wise independent distributions. These results are all in fact special cases of a general framework where a group acts on a set. In the aforementioned case, the group of permutations acts on tuples of k elements. We prove all the above results in the general setting of the action of a finite group on a finite set.
AB - A family of permutations in S n is k-wise independent if a uniform permutation chosen from the family maps any distinct k elements to any distinct k elements equally likely. Efficient constructions of k-wise independent permutations are known for k = 2 and k = 3, but are unknown for k ≥ 4. In fact, it is known that there are no nontrivial subgroups of S n for n ≥ 25 which are 4-wise independent. Faced with this adversity, research has turned towards constructing almost k-wise independent families, where small errors are allowed. Optimal constructions of almost k-wise independent families of permutations were achieved by several authors. Our first result is that any such family with small enough error is statistically close to a distribution which is perfectly k-wise independent. This allows for a simplified analysis of algorithms: an algorithm which uses randomized permutations can be analyzed assuming perfect k-wise independence, and then applied to an almost k-wise independent family. In particular, it allows for an oblivious derandomization of two-sided randomized algorithms which work correctly given any k-wise independent distribution of permutations. Another model is that of weighted families of permutations, or equivalently distributions of small support. We establish two results in this model. First, we show that a small random set of n O(k) permutations w.h.p supports a k-wise independent distribution. We then derandomize this by showing that any almost 2k-wise independent family supports a k-wise independent distribution. This allows for oblivious derandomization of algorithms for search problems which work correctly given perfect k-wise independent distributions. These results are all in fact special cases of a general framework where a group acts on a set. In the aforementioned case, the group of permutations acts on tuples of k elements. We prove all the above results in the general setting of the action of a finite group on a finite set.
UR - http://www.scopus.com/inward/record.url?scp=84865283248&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84865283248&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-32512-0_30
DO - 10.1007/978-3-642-32512-0_30
M3 - Conference contribution
AN - SCOPUS:84865283248
SN - 9783642325113
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 350
EP - 361
BT - Approximation, Randomization, and Combinatorial Optimization
T2 - 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012
Y2 - 15 August 2012 through 17 August 2012
ER -