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
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)