ACO The ACO Seminar (2017–2018)

Sep. 14, 3:30pm, Wean 8220
Freddie Manners, Stanford
Sums of permutations


Suppose G is an abelian group of order N, e.g. 𝔽2n, and π1, π2: {1,...,N} are permutations (i.e., bijections) chosen uniformly at random. Consider the function π12: {1,...,N} → G. How closely does it resemble a random function? In particular, what is the chance that it is again a permutation? What about π1 + π2 + π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.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.

Back to the ACO home page