Add to Outlook calendar Add to Google calendar

APRG Seminar

Title: Algorithmic Discrepancy Theory: A Tale of Combinatorics, Probability, Convex Geometry and Algorithms
Speaker: Abhishek Shetty (University of California, Berkeley, USA)
Date: 04 July 2024
Time: 3 pm
Venue: LH-1, Mathematics Department

Discrepancy theory is a well-studied area in mathematics, concerned with the question of partitioning geometry and combinatorial objects in balanced subsets. Starting from seminal works of Spencer, Banaszczyk, Gluskin amongst others, deep connections between the area and other areas in mathematics such as convex geometry and probability were established. But, for most of its history, the arguments establishing the existence of good partitions were non-constructive, even believed to be fundamentally non-algorithmic.

But, the past decade has seen a flurry of work in algorithmic discrepancy theory, leading to efficient algorithms for several of the most famous settings in discrepancy theory. Perhaps surprisingly, these algorithmic techniques have further strengthened the connection between discrepancy and other areas such as convex geometry and probability.

In this talk, we will survey recent results and techniques in algorithmic discrepancy with the aim to convey connections to various areas. Time permitting, we will end with natural conjectures that would lead to progress on long standing conjectures in discrepancy theory.

No prior exposure to algorithms, computer science or discrepancy will be assumed.

Contact: +91 (80) 2293 2711, +91 (80) 2293 2265 ;     E-mail: chair.math[at]iisc[dot]ac[dot]in
Last updated: 15 Jul 2024