Product rules in Semidefinite Programming

Mario Szegedy


In recent years we witness the proliferation of semidefinite programming

bounds in combinatorial optimization, quantum computing, and even in

complexity theory. In these bounds the key observation is often the fact

that the new parameter in question is multiplicative with respect to the

product of the problem instances. 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 in Shannon capacity paper of L. Lovasz and

XOR game paper of R. Cleve, W. Slofstra, F. Unger and S. Upadhyay.

We find conditions under which the product rule always holds and give

examples for cases when the product rule does not hold.


(Joint with Rajat Mittal and Troy Lee)