THEORY SEMINAR: Sudarshan Shyam on "A new lower bound for multi-color discrepancy with applications to fair division, Sudarshan Shyam, Aarhus University
- Event Type
- Seminar/Symposium
- Sponsor
- Michael A. Forbes
- Location
- Siebel 3401
- Date
- Nov 4, 2024 10:00 am
- Speaker
- Sudarshan Shyam
- Views
- 62
- Originating Calendar
- Siebel School Speakers Calendar
THEORY SEMINAR: Please join us on Nov 4th, 2024, at 10am in the Siebel 3401 where Sudarshan Shyam, from Aarhus University, will give a talk, “A new lower bound for multi-color discrepancy with applications to fair division”. Please see their abstract below:
Abstract: A classical problem in combinatorics seeks colorings of low discrepancy. More concretely, the goal is to color the elements of a set system so that the number of appearances of any color among the elements in each set is as balanced as possible. We present a new lower bound for multi-color discrepancy. This result improves the previously best-known lower bound of Ω(sqrt(n/k)) of Doerr and Srivastav [2003] and may have several applications. Here, we explore its implications on the feasibility of fair division concepts for instances with n agents having valuations for a set of indivisible items.