Semidefinite Programming (with focus on product rules)

Mario Szegedy
Rutgers University
 
Wednesday, September 05, 2007 11:00am - 12:00pm
DIMACS Center, CoRE Bldg, Room 431, Busch Campus

Abstract

In recent years we witness the proliferation of semidefinite programming bounds in combinatorial optimization, quantum computing, and even in complexity theory. Examples to such bounds include the semidefinite relaxation for the maximal cut problem (GW), and the quantum value of multi-prover interactive games. The first semidefinite programming bound, which gained fame, arose in the late seventies and was due to Laszlo Lovasz, who used his theta number to compute the Shannon capacity of the five cycle graph. As in Lovasz's upper bound proof for the Shannon capacity and in other situations the key observation is often the fact that the new parameter in question is multiplicative with respect to the product of the problem instances. In a recent result R. Cleve, W. Slofstra, F. Unger and S. Upadhyay show that the quantum value of XOR games multiply under parallel composition. This result together with strengthens the parallel repetition theorem of Ran Raz for XOR games. Our goal is to classify those semidefinite programming instances for which the optimum is multiplicative under a naturally defined product operation. The product operation we define generalizes the ones used by Lovasz and Cleve et. al. We find conditions under which the product rule always holds and give examples for cases when the product rule does not hold.

This is joint work with Rajat Mittal, Rutgers University.