Joint Theory Lunch Seminar / Speaking Skills Talk - William He

— 1:00pm

Location:
In Person - Reddy Conference Room, Gates Hillman 4405

Speaker:
WILLIAM HE, Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://wrhe.github.io/

Pseudorandomness Properties of Random Reversible Circuits

Motivated by cryptography, quantum information theory, circuit complexity, and derandomization, there has been significant recent progress in the study of random permutations resembling a completely random permutation of n-bit strings. Of particular interest is the case where the measure of "resemblance" is approximation of the k-th moments of the matrix representations. Such random permutations are known as approximate k-wise independent permutations. In this talk I will discuss some recent results that show that small random reversible circuits compute approximate k-wise independent permutations:   

i) We show that a random reversible circuit with Õ(nk) gates computes a constant-approximate k-wise independent permutation. This result implies a generalization of Shannon's circuit lower bound argument.   

ii) We show that a random reversible circuit with Õ(nk2) layers of 1D-local gates arranged in a brickwork architecture computes a exp(– nk)-approximate k-wise independent permutation; connections to block ciphers exist. 

Based on joint works with William Gay (CMU), Lucas Gretta (Berkeley), Nicholas Kocurek (CMU), Ryan O'Donnell (CMU), Angelos Pelecanos (Berkeley). 

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement

Event Website:
https://www.cs.cmu.edu/~theorylunch/abstractsHTML/20240925.html