Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
Freddie Manners Stanford University Title: Sums of permutations Abstract: Suppose G is an abelian group of order N, e.g. $\mathbb{F}$, and $\pi$ _{2}^{n}_{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. |