CMU Campus
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
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.

Date: Thursday, September 14, 2017
Time: 3:30 pm
Location: Wean Hall 8220
Submitted by:  Bukh
Note: Before the talk, at 3:10 pm, there will be tea and cookies in Wean Hall 6220.