Conference Program
PLENARY AND SEMIPLENARY TALKS
Friday, August 24, 09:00 – 09:50 h, H0105:
Nikhil Bansal: Semidefinite Optimization in Discrepancy Theory
Chair: Friedrich Eisenbrand
Abstract:
The concept of discrepancy is intimately related to several fundamental topics in mathematics and theoretical computer science, and deals with the following type of question. Given a collection of sets on some elements, color each element red or blue such that each set in the collection is colored as evenly as possible. Recently, there have been several new developments in discrepancy theory based on connections to semidefinite programming. This connection has been useful in several ways. It gives efficient polynomial time algorithms for several problems for which only nonconstructive results were previously known. It also leads to several new structural results in discrepancy itself, such as tightness of the socalled determinant lower bound, improved bounds on the discrepancy of the union of set systems and so on. We will give a brief survey of these results, focussing on the main ideas and the techniques involved.
Biographical sketch:
Nikhil Bansal is an Associate Professor in the Department of Mathematics and Computer Science at Eindhoven University of Technology. He obtained his PhD from Carnegie Mellon University in 2003, and worked at the IBM T.J. Watson Research Center until 2011, where he also managed the Algorithms group. His main research interests are the design and analysis of approximation and online algorithms. For his work, he has coreceived best paper awards at FOCS 2011, ESA 2011 and ESA 2010, and also IBM Research best paper awards for 2007 and 2010.
