Pseudorandom permutations, unitaries, and more

Add to your list(s) Download to your calendar using vCal

• Ryan O'Donnell (Carnegie Mellon University)
• Monday 08 April 2024, 14:00-15:00
• Seminar Room 1, Newton Institute.

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:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.