SDP Gaps from Pairwise Independence

by Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani

Theory of Computing, Volume 8(12), pp. 269-289, 2012

Bibliography with links to cited articles

[1]    Mikhail Alekhnovich, Sanjeev Arora, and Iannis Tourlakis: Towards strong nonapproximability results in the Lovász-Schrijver hierarchy. In Proc. 37th STOC, pp. 294–303. ACM Press, 2005. [doi:10.1145/1060590.1060634]

[2]   Mikhail Alekhnovich, Sanjeev Arora, and Iannis Tourlakis: Towards strong nonapproximability results in the Lovász-Schrijver hierarchy. Comput. Complexity, 20(4):615–648, 2011. [doi:10.1007/s00037-011-0027-z]

[3]   Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis: Proving integrality gaps without knowing the linear program. Theory of Computing, 2(1):19–51, 2006. Preliminary version in FOCS’02. [doi:10.4086/toc.2006.v002a002]

[4]   Per Austrin and Johan Håstad: Randomly supported independence and resistance. SIAM J. Comput., 40(1):1–27, 2011. Preliminary version in STOC’09. [doi:10.1137/100783534]

[5]   Per Austrin and Elchanan Mossel: Approximation resistant predicates from pairwise independence. Comput. Complexity, 18(2):249–271, 2009. Preliminary version in CCC’08. [doi:10.1007/s00037-009-0272-6]

[6]    Mohammad Hossein Bateni, Moses Charikar, and Venkatesan Guruswami: MaxMin allocation via degree lower-bounded arborescences. In Proc. 41st STOC, pp. 543–552. ACM Press, 2009. [doi:10.1145/1536414.1536488]

[7]   Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan: Detecting high log-densities—an O(n14) approximation for densest k-subgraph. In Proc. 42nd STOC, pp. 201–210. ACM Press, 2010. [doi:10.1145/1806689.1806719]

[8]   Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi: Rank bounds and integrality gaps for cutting planes procedures. Theory of Computing, 2(4):65–90, 2006. Preliminary version in FOCS’03. [doi:10.4086/toc.2006.v002a004]

[9]   Moses Charikar, Konstantin Makarychev, and Yury Makarychev: Integrality gaps for Sherali–Adams relaxations. In Proc. 41st STOC, pp. 283–292. ACM Press, 2009. [doi:10.1145/1536414.1536455]

[10]   Eden Chlamtac: Approximation algorithms using hierarchies of semidefinite programming relaxations. In Proc. 48th FOCS, pp. 691–701. IEEE Comp. Soc. Press, 2007. [doi:10.1109/FOCS.2007.72]

[11]   Eden Chlamtac and Gyanit Singh: Improved approximation guarantees through higher levels of SDP hierarchies. In Proc. 11th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’08), volume 5171 of Lecture Notes in Computer Science, pp. 49–62. Springer, 2008. [doi:10.1007/978-3-540-85363-3_5]

[12]   Lars Engebretsen and Jonas Holmerin: More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP. Random Structures Algorithms, 33:497–514, 2008. Preliminary version in STACS’05. [doi:10.1002/rsa.20226]

[13]   Uriel Feige and Robert Krauthgamer: The probable value of the Lovász-Schrijver relaxations for maximum independent set. SIAM J. Comput., 32(2):345–370, 2003. [doi:10.1137/S009753970240118X]

[14]   Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu: Linear programming relaxations of maxcut. In Proc. 18th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’07), pp. 53–61. SIAM, 2007. [ACM:1283390]

[15]   Konstantinos Georgiou, Avner Magen, Toniann Pitassi, and Iannis Tourlakis: Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovász-Schrijver hierarchy. SIAM J. Comput., 39(8):3553–3570, 2010. Preliminary version in FOCS’07. [doi:10.1137/080721479]

[16]    Venkatesan Guruswami and Prasad Raghavendra: Constraint satisfaction over a non-Boolean domain: Approximation algorithms and Unique-Games hardness. In Proc. 11th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’08), pp. 77–90. Springer, 2008. [doi:10.1007/978-3-540-85363-3_7]

[17]   Jean B. Lasserre: An explicit equivalent positive semidefinite program for nonlinear 0-1 programs. SIAM J. Optim., 12(3):756–769, 2002. [doi:10.1137/S1052623400380079]

[18]   Monique Laurent: A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0-1 programming. Math. Oper. Res., 28(3):470–496, August 2003. [doi:10.1287/moor.28.3.470.16391]

[19]   L. Lovász and A. Schrijver: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim., 1(2):166–190, May 1991. [doi:10.1137/0801013]

[20]   Avner Magen and Mohammad Moharrami: Robust algorithms for max independent set on minor-free graphs based on the Sherali–Adams hierarchy. In Proc. 12th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’09), pp. 258–271, Berlin, Heidelberg, 2009. Springer-Verlag. [doi:10.1007/978-3-642-03685-9_20]

[21]   Claire Mathieu and Alistair Sinclair: Sherali-Adams relaxations of the matching polytope. In Proc. 41st STOC, pp. 293–302. ACM Press, 2009. [doi:10.1145/1536414.1536456]

[22]   Prasad Raghavendra: Optimal algorithms and inapproximability results for every CSP? In Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [doi:10.1145/1374376.1374414]

[23]   Prasad Raghavendra and David Steurer: Integrality gaps for strong SDP relaxations of unique games. In Proc. 50th FOCS, pp. 575–585. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.73]

[24]   Alex Samorodnitsky and Luca Trevisan: Gowers uniformity, influence of variable, and PCPs. SIAM J. Comput., 39:323–360, 2009. Preliminary version in STOC’06. [doi:10.1137/070681612]

[25]   Alex Samorodnitsky and Luca Trevisan: A PCP charcaterization of NP with optimal amortized query complexity. In Proc. 32nd STOC, pp. 191–199. ACM Press, 2010. [doi:10.1145/335305.335329]

[26]   Grant Schoenebeck: Linear level Lasserre lower bounds for certain k-CSPs. In Proc. 49th FOCS, pp. 593–602. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.74]

[27]   Grant Schoenebeck, Luca Trevisan, and Madhur Tulsiani: A linear round lower bound for Lovász-Schrijver SDP relaxations of vertex cover. In Proc. 22nd IEEE Conf. on Computational Complexity (CCC’07), pp. 205–216. IEEE Comp. Soc. Press, 2007. [doi:10.1109/CCC.2007.2]

[28]   Grant Schoenebeck, Luca Trevisan, and Madhur Tulsiani: Tight integrality gaps for Lovász-Schrijver LP relaxations of vertex cover and max cut. In Proc. 39th STOC, pp. 302–310. ACM Press, 2007. [doi:10.1145/1250790.1250836]

[29]   Hanif D. Sherali and Warren P. Adams: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math., 3(3):411–430, August 1990. [doi:10.1137/0403036]

[30]   Iannis Tourlakis: Towards optimal integrality gaps for hypergraph vertex cover in the Lovász-Schrijver hierarchy. In Proc. 8th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’05), volume 3624, pp. 233–244. Springer, 2005. [doi:10.1007/11538462_20]

[31]   Iannis Tourlakis: New lower bounds for vertex cover in the Lovász-Schrijver hierarchy. In Proc. 21st IEEE Conf. on Computational Complexity (CCC’06), pp. 170–182. IEEE Comp. Soc. Press, 2006. [doi:10.1109/CCC.2006.28]

[32]   Madhur Tulsiani: CSP gaps and reductions in the Lasserre hierarchy. In Proc. 41st STOC, pp. 303–312. ACM Press, 2009. [doi:10.1145/1536414.1536457]