Computer Science/Discrete Mathematics Seminar I

Semidefinite programming bounds are widely used in combinatorial optimization, quantum computing and complexity theory. The first semidefinite programming bound to gain fame is the so-called theta number developed by Lov\'asz to compute the Shannon capacity of the five-cycle graph. The semidefinite relaxation for the maximal cut problem has led to the near ubiquitous use of semidefinite programming in designing approximation algorithms. Semidefinite programming has also been used to understand the value of interactive games played in parallel and quantum value of multi-prover interactive games. In many of these cases, for example to analyze the Shannon capacity or the value of games played in parallel, a key property of the semidefinite program bound is that it is multiplicative with respect to taking the product of instances. In this talk, we attempt to develop a general theory to explain when the optimum of a semidefinite program is multiplicative under a naturally defined product operation. We find sufficient conditions for the product rule to hold, and also discuss why in some cases it does not hold. Our framework is general enough to explain many semidefinite product theorems in the literature.