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

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.