Description

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: https://arxiv.org/abs/2101.04036