MIT PhD Thesis Defense: Mehtaab Sawhney

Building 2, Room 449

Presenter: Mehtaab SawhneyTitle: Probabilistic and Analytic Methods in CombinatoricsAbstract: The defense will center on fast algorithms for discrepancy theory. Discrepancy theory is broadly concerned with the following problem; given a set of objects, we aim to partition them into pieces which are “roughly equal”. We will focus specifically on vector balancing: given a set of vectors, one seeks to divide them into two parts with approximately equal sum.Important results in this area, including Spencer’s six standard deviations suffice and Banaszczyk's results towards the Komlós conjecture, were originally purely existential. However, since work of Bansal from 2010, it has become clear that such existential results can often be made algorithmic. We will explain a pair of such results. The first concerns bounds for online vector balancing obtained via a certain Gaussian fixed point random walk. The second gives an algorithmic form of Spencer's theorem that runs in near input sparsity time.All are welcome!