### DIMACS Theoretical Computer Science Seminar

Title: Product Theorem via semidefinite programming

Speaker: ** Rajat Mittal**, Rutgers University

Date: Wednesday, March 5, 2008 11:00-12:00pm

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

Abstract:

The tendency of semidefinite programs to compose perfectly under
product has been exploited
many times in complexity theory: for example, by Lovasz to determine
the Shannon capacity of
the pentagon; to show a direct sum theorem for non-deterministic
communication complexity and
direct product theorems for discrepancy; and in interactive proof
systems to show parallel
repetition theorems for restricted classes of games.

Despite all these examples of product theorems---some going back
nearly thirty years---it was
only recently that Mittal and Szegedy began to develop a general
theory to explain when and
why semidefinite programs behave perfectly under product. This
theory captured many examples in
the literature, but there were also some notable exceptions which it
could not explain---namely, an
early parallel repetition result of Feige and Lovasz, and a direct
product theorem for the
discrepancy method of communication complexity by Lee, Shraibman, and
Spalek.
In this talk we explain these cases.

Joint work with Troy Lee.