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.