The ACO Seminar (2017–2018)

Suppose G is an abelian group of order N, e.g. 𝔽₂ⁿ, and π₁, π₂: {1,...,N} are permutations (i.e., bijections) chosen uniformly at random. Consider the function π₁+π₂: {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 π₁ + π₂ + π₃?

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.