University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Pseudorandom permutations, unitaries, and more

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Pseudorandom permutations, unitaries, and more

Download to your calendar using vCal

If you have a question about this talk, please contact nobody.

OOEW04 - Structure and Randomness - a celebration of the mathematics of Timothy Gowers

Suppose we make a reversible Boolean circuit on n bits by randomly combining 3-bit reversible gates.  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⊗k] is close to what it would be if P were a uniformly random permutation.  Can this be quantitatively improved?  What about the analogous question for qubits and random quantum circuits?  Or random orthogonal circuits?  And what does this have to do with cryptography, Ramanujan graphs, and black holes? Joint work with William He (Carnegie Mellon), Pedro Paredes (Princeton), and Rocco Servedio (Columbia).

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Goldsmiths 1, Lecture Theatre, Department of Materials Science & Metallurgy Castle Teaching Room Venue TBC, Pembroke College

Other talks

TBC External Seminar - Michael Raissig TBC Security Cooperation within Government and between Governments The Inaccessible Game Scattering Plenty: the people who made the modern countryside Talk TBC
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity