DIMACS Theoretical Computer Science Seminar

Title: Approximation algorithms via matrix covers

Speaker: Noga Alon, Tel Aviv University

Date: Wednesday, October 9, 2013 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


I will describe a general technique for obtaining approximate solutions of hard quadratic optimization problems using economical covers of high dimensional sets by small cubes. The analysis of the method leads to intriguing algorithmic, combinatorial, extremal, geometric and probabilistic questions.

Based on joint work with Lee, Shraibman and Vempala.

See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F13/