Skip to content Skip to navigation
Seminar
10/9/2013 11:00 am
CoRE 431

Approximation algorithms via matrix covers

Noga Alon, Tel Aviv University, IAS

Organizer(s): Swastik Kopparty and Shubhangi Saraf

Abstract

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.