Fall 2021

CCSI Weekly Seminar: Stein's Method, Second Moments, and Discrepancy Minimization

Tuesday, November 30th, 2021, 11:00 am12:00 pm

Add to Calendar


Dylan Altschuler (New York University)


Room 116

Discrepancy is a combinatorial optimization problem with applications ranging from integer rounding to group testing. We study the average case: given a wide matrix with independent Bernoulli entries, what is its discrepancy? The sparse regime presents technical challenges that break standard tools. 

We will present Stein's Method of Exchangeable Pairs and explain how it can be combined with the Second Moment Method to understand discrepancy at any sparsity. Stein's method is a modern technique for comparing distributions. The second moment method is a classical tool for investigating level sets of random functions. 

Joint work with Jonathan Niles-Weed: