Product rules in Semidefinite Programming
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
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)