|
Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
Stanford University Title: Sums of permutations Abstract: Suppose G is an abelian group of order N, e.g. $\mathbb{F}$2n, and $\pi$ 1, $\pi$ 2: {1,...,N} are permutations (i.e., bijections) chosen uniformly at random. Consider the function $\pi$ 1 + $\pi$ 2: {1,...,N} $\rightarrow$ G. How closely does it resemble a random function? In particular, what is the chance that it is again a permutation? What about $\pi$ 1 + $\pi$ 2 + $\pi$ 3? The middle question, thought of as a free-standing counting problem, was the subject of a long-running conjecture due to Vardi. The outer two have applications in security and pseudorandomness, connecting pseudorandom functions (PRFs) and pseudorandom permutations (PRPs). I will discuss joint work with Sean Eberhard and Rudi Mrazović, as well as extensions due to Eberhard, which give precise answers to some of these questions. |
