BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Pseudorandom permutations\, unitaries\, and more - Ryan O'Donnell 
 (Carnegie Mellon University)
DTSTART:20240408T130000Z
DTEND:20240408T140000Z
UID:TALK213856@talks.cam.ac.uk
DESCRIPTION:Suppose we make a reversible Boolean circuit on n bits by rand
 omly combining 3-bit reversible gates.&nbsp\; A 1996 paper of Gowers shows
  that with poly(n\,k) many gates\, the resulting permutation P on {0\,1}n 
 is nearly "k-wise uniform"\; this means that E[P&otimes\;k] is close to wh
 at it would be if P were a uniformly random permutation.&nbsp\; Can this b
 e quantitatively improved?&nbsp\; What about the analogous question for qu
 bits and random quantum circuits?&nbsp\; Or random orthogonal circuits?&nb
 sp\; And what does this have to do with cryptography\, Ramanujan graphs\, 
 and black holes?\nJoint work with William He (Carnegie Mellon)\, Pedro Par
 edes (Princeton)\, and Rocco Servedio (Columbia).
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR