Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
Newsletter: @DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar - April 21
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar - April 21
Location: GB 221
Shachar Lovett, The Institute of Advanced Study, Princeton, NJ
Title: Almost k-wise vs. perfect k-wise independent permutations
Abstract:
A family of permutations on n elements is k-wise independent if it uniformly maps distinct k-tuples to distinct k-tuples. Constructions of small k-wise independent families of permutations are only known for k=1,2,3, and it is known that nontrivial subgroups of S_n cannot work for k>=4 (and n>=25). Thus, research has turned towards constructing almost-k-wise independent families, where small errors are allowed. Optimal almost-k-wise families were given by several authors.
Our first result is that any such family (with small enough error) is statistically close to a distribution over permutations which is 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 any $k$-wise independent distributions of permutations.
Joint work with Noga Alon.