A Additional related works

Lemma 5 implies a simple closed form expression for the expected error in the CSSP . Using Lemma 5, the expected loss is given by: E " Er We will use the following standard determinantal summation identity (see Theorem 2.1 in Kulesza & Lemma 7. F or any n ˆ n matrix K, we have det p I ` K q" ÿ We now proceed with the proof of Lemma 5 (restated below for convenience). We will next define an alternate sequence of eigenvalues which is in some sense "worst-case", by " r l, and obtain: ÿ Newton's inequalities imply that: 1 e The results of Deshpande et al. ( 2006) and Guruswami & Sinop ( 2012) establish that A q and we let b " min t k s, n k u, then for any 0 Now, the result follows easily by invoking Lemma 3: E " Er We provide the proof by splitting it into two cases. Further using u " k s, we can call upon Theorem 1 to get, With p k { 60, we get: 12 pk k 2 p 12 pk k k { 30 " 12 p 1 1 { 30 360 29 p. The overall bound thus becomes 61 p . We will use u " k s .