Speaker: Luca Trevisan University of California, Berkeley
Time: 2008-03-26 15:30-2008-03-26 16:30
Venue: FIT Building 4-603, Tsinghua University

Abstract:

Lovasz and Schrijver define hierarchies of operators, which act on simple linear programs to produce stronger linear and semidefinite relaxations for optimization problems. A constant number of applications (rounds) of these operators are known to capture most known linear programming (LP) and semidefinite programming (SDP) based approximation algorithms.
        We prove integrality gaps for these hierarchies when applied to the basic LP relaxation for Vertex Cover. We show even after \Omega(n) applications of these operators the integrality gap remains at least 2-\epsilon in the hierarchy of LPs and at least 7/6-\epsilon in the hierarchy of SDPs. Since r rounds take time n^{O(r)} to solve, this gives lower bounds even for exponential time algorithms based on programs within these hierarchies.
        This is joint work with Grant Schoenebeck and Madhur Tulsiani.
 

Short Bio:

 Luca Trevisan is an associate professor of computer science at U.C.Berkeley. Luca received his Laurea (BSc) degree in 1993 and his Dottorato (PhD) in 1997, both from the University of Rome La Sapienza. Before coming to Berkeley in 2000, Luca was a post-doc at MIT and at DIMACS, and an assistant professor at Columbia University.
        Luca's research is in theoretical computer science, and most of his work has related to pseudorandomness, average-case complexity, explicit combinatorial constructions, and approximability of combinatorial optimization problems.
        Luca received the STOC 1997 student paper award (now known as the Danny Lewin award), the 2000 Oberwolfach Prize, and the 2000 Sloan Fellowship.He lectured in the 2000 IAS/PCMI Summer School and he was an invited speaker at the 2006 International Congress of Mathematicians in Madrid.