Paper Info
Title
Product Rules in Semidefinite Programming
Abstract
In recent years we witness the proliferation of semidefinite programming bounds in combinatorial optimization (1,5,8), quantum com- puting (9,2,3,6,4) and even in complexity theory (7). Examples to such bounds include the semidefinite relaxation for the maximal cut problem (5), and the quantum value of multi-prover interactive games (3,4). The first semidefinite programming bound, which gained fame, arose in the late seventies and was due to Laszlo Lovasz (11), 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 prob- lem 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 (4). This result together with (3) strengthens the parallel repetition theorem of Ran Raz (12) for XOR games. Our goal is to classify those semidefinite programming instances for which the opti- mum is multiplicative under a naturally defined product operation. The product operation we define generalizes the ones used in (11) and (4). We find conditions under which the product rule always holds and give examples for cases when the product rule does not hold. and that the independence number of any graph G is upper bounded by a cer- tain semidefinite programming bound, that he called #(G). Lovasz showed that #(C5) = √ 5, and that # is multiplicative: #(G × G') = #(G) × #(G'), for any two graphs, G and G'. These facts together with the super-multiplicativity of stbl(G) are clearly sufficient to imply the conjecture. 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 (4). The quantum value of a XOR game arises as the solution of an associated semidefinite program (14) and upper bounds the classical value of the game. The result, when combined with the fact there is a relation between the classical and quantum values of a multi-prover game (3) gives a new proof for the parallel repetition
Year
DOI
Venue
2007
10.1007/978-3-540-74240-1_38
Fundamentals of Computation Theory
Keywords
Field
DocType
quantum computing,product operation,product rule,semidefinite programming bound,semidefinite programming instance,shannon capacity,semidefinite relaxation,semidefinite programming,quantum value,xor game,combinatorial optimization,upper bound
Discrete mathematics,Combinatorics,Multiplicative function,Product rule,Upper and lower bounds,Quantum computer,Cycle graph,Combinatorial optimization,Mathematics,Semidefinite programming,Maximum cut
Conference
Volume
ISSN
ISBN
4639
0302-9743
3-540-74239-5
Citations 
PageRank 
References 
10
0.77
11
Authors
2
Name
Order
Citations
PageRank
Rajat Mittal117017.59
Mario Szegedy23358325.80