Scientific Program

Semi-plenary Lecture

Program -> Plenary and Semi-Plenary -> Fri.9:00.H 0105 title only | abstract | bio sketch

Friday, 9:00 - 9:50 h, H 0105


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 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.

 

 

Program -> Plenary and Semi-Plenary -> Fri.9:00.H 0105 title only | abstract | bio sketch

  Getting California Loans Online should be thought of many times. But at the same time, it acts only with sexual arousal. Cheap Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.