BARC talk by Rex Lei

Thursday, June 25, 2026, Rex Lei, Postdoc MPI Saarbrücken, Germany, will be giving at talk on "Replicability and Differential Privacy". 

Abstract: 
In 2022, his co-authors and Rex Lei introduced a mathematical definition for replicable learning algorithms. Formally, a randomized algorithm A(S;r) is rho-replicable if, with high probability, the algorithm outputs the exact same answer when run with the same random string r on two sample sets S_1 and S_2 each drawn i.i.d. from a distribution D. 

In this talk, he will introduce replicability and discuss its basic properties. Then, he will describe their work connecting replicability and differential privacy. They gave sample-efficient reductions between replicable algorithms and differentially private algorithms. Their reductions hold for statistical problems (i.e., problems in which correctness is a function only of the underlying sample distribution) over finite output domains. Although their DP-to-replicability conversion is not computationally efficient, they showed that this is necessary under public-key cryptography assumptions. Furthermore, they showed that the existence of one-way function inverters would imply efficient correlated sampling, making their reduction computationally efficient as well. 

The talk will focus on the high-level ideas behind these two notions, not the technical details.

Based on joint work with Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell in STOC 2023. 

Bio:
Rex Lei is a postdoc at the Max-Planck Institute for Informatics. Rex's work is primarily in learning theory and robustness for algorithms. Rex received a PhD in 2024 at UC San Diego, advised by Russell Impagliazzo. 

Host:
Prateek Dwivedi