کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657689 | 690550 | 2005 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Simple permutations mix well
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study the random composition of a small family of O(n3) simple permutations on {0,1}n. Specifically, we ask what is the number of compositions needed to achieve a permutation that is close to k-wise independent. We improve on a result of Gowers [An almost m-wise independent random permutation of the cube, Combin. Probab. Comput. 5(2) (1996) 119-130] and show that up to a polylogarithmic factor, n3k3 compositions of random permutations from this family suffice. We further show that the result applies to the stronger notion of k-wise independence against adaptive adversaries. This question is essentially about the rapid mixing of the random walk on a certain graph, and we approach it using a new technique to construct canonical paths. We also show that if we are willing to use a much larger family of simple permutations then we can guarantee closeness to k-wise independence with fewer compositions and fewer random bits.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 348, Issues 2â3, 8 December 2005, Pages 251-261
Journal: Theoretical Computer Science - Volume 348, Issues 2â3, 8 December 2005, Pages 251-261
نویسندگان
Shlomo Hoory, Avner Magen, Steven Myers, Charles Rackoff,