Conference Program


 (Add to Calendar)  Friday, August 24, 09:00 – 09:50 h, H0105:

Nikhil Bansal: Semidefinite Optimization in Discrepancy Theory

Chair: Friedrich Eisenbrand



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 non-constructive results were previously known. It also leads to several new structural results in discrepancy itself, such as tightness of the so-called 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 co-received best paper awards at FOCS 2011, ESA 2011 and ESA 2010, and also IBM Research best paper awards for 2007 and 2010.

  There are three major facts that should be watched out for in all payday loans in the United States. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.