On Polyhedral Approximations of the Positive Semidefinite Cone

References

• [1] Ahmadi AA, Majumdar A (2019) DSOS and SDSOS optimization: More tractable alternatives to sum of squares and semidefinite optimization. SIAM J. Appl. Algebra Geometry 3(2):193–230.Crossref, Google Scholar
• [2] Anjos MF, Lasserre JB (2011) Handbook on Semidefinite, Conic and Polynomial Optimization, vol. 166 (Springer, Boston).Google Scholar
• [3] Aubrun G, Szarek S (2017) Alice and Bob Meet Banach: The Interface of Asymptotic Geometric Analysis and Quantum Information Theory, vol. 223 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [4] Aubrun G, Szarek S (2017) Dvoretzky’s theorem and the complexity of entanglement detection. Discrete Anal. 2017:1.Google Scholar
• [5] Barvinok A, Veomett E (2006) The computational complexity of convex bodies. Preprint, October 10, https://arxiv.org/abs/math/0610325.Google Scholar
• [6] Beckner W (1975) Inequalities in Fourier analysis. Ann. of Math. 102(1):159–182.Crossref, Google Scholar
• [7] Beckner W (1992) Sobolev inequalities, the Poisson semigroup, and analysis on the sphere Sn. Proc. Natl. Acad. Sci. USA 89(11):4816–4819.Crossref, Google Scholar
• [8] Ben-Tal A, Nemirovski A (2001) On polyhedral approximations of the second-order cone. Math. Oper. Res. 26(2):193–205.Link, Google Scholar
• [9] Bonami A (1970) Étude des coefficients de Fourier des fonctions de Lp(G). Ann. Inst. Fourier 20(2):335–402.Crossref, Google Scholar
• [10] Boyd S, El Ghaoui L, Feron E, Balakrishnan V (1994) Linear Matrix Inequalities in System and Control Theory, vol. 15 (SIAM, Philadelphia).Crossref, Google Scholar
• [11] Braun G, Fiorini S, Pokutta S, Steurer D (2012) Approximation limits of linear programs (beyond hierarchies). IEEE 53rd Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 480–489.Google Scholar
• [12] Candes EJ, Strohmer T, Voroninski V (2013) Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming. Comm. Pure Appl. Math. 66(8):1241–1274.Crossref, Google Scholar
• [13] Chan SO, Lee JR, Raghavendra P, Steurer D (2013) Approximate constraint satisfaction requires large LP relaxations. IEEE 54th Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 350–359.Google Scholar
• [14] Fawzi H (2016) Power and limitations of convex formulations via linear and semidefinite programming lifts. Unpublished doctoral dissertation, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• [15] Fawzi H, Gouveia J, Parrilo PA, Robinson RZ, Thomas RR (2015) Positive semidefinite rank. Math. Programming 153(1):133–177.Crossref, Google Scholar
• [16] Fiorini S, Massar S, Pokutta S, Tiwary HR, Wolf RD (2015) Exponential lower bounds for polytopes in combinatorial optimization. J. ACM 62(2):17.Crossref, Google Scholar
• [17] Gouveia J, Parrilo PA, Thomas RR (2013) Lifts of convex sets and cone factorizations. Math. Oper. Res. 38(2):248–264.Link, Google Scholar
• [18] Kaibel V (2011) Extended formulations in combinatorial optimization. Preprint, submitted April 6, https://arxiv.org/abs/1104.1023.Google Scholar
• [19] Klartag B, Regev O (2011) Quantum one-way communication can be exponentially stronger than classical communication. Proc. 43rd Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 31–40.Google Scholar
• [20] Kothari PK, Meka R, Raghavendra P (2017) Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. Proc. 49th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 590–603.Google Scholar
• [21] Laurent M, Rendl F (2005) Semidefinite programming and integer programming. Discrete Optimization. Handbooks in Operations Research and Management Science, vol. 12 (Elsevier, Amsterdam), 393–514.Google Scholar
• [22] Litvak AE, Rudelson M, Tomczak-Jaegermann N (2014) On approximation by projections of polytopes with few facets. Israel J. Math. 203(1):141–160.Crossref, Google Scholar
• [23] O’Donnell R (2014) Analysis of Boolean Functions (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [24] Pashkovich K (2012) Extended formulations for combinatorial polytopes. Unpublished doctoral dissertation, Otto-von-Guericke-Universität Magdeburg, Magdeburg, Germany.Google Scholar
• [25] Rothvoß T (2014) The matching polytope has exponential extension complexity. Proc. 46th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 263–272.Google Scholar
• [26] Sivaramakrishnan KK (2002) Linear programming approaches to semidefinite programming problems. Unpublished doctoral dissertation, Rensselaer Polytechnic Institute, Troy, NY.Google Scholar
• [27] Todd MJ (2001) Semidefinite optimization. Acta Numerica 10:515–560.Crossref, Google Scholar
• [28] Vandenberghe L, Boyd S (1996) Semidefinite programming. SIAM Rev. 38(1):49–95.Crossref, Google Scholar
• [29] Vershynin R (2018) High-Dimensional Probability: An Introduction with Applications in Data Science, vol. 47 (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [30] Wang Y, Tanaka A, Yoshise A (2019) Polyhedral approximations of the semidefinite cone and their applications. Preprint, submitted May 1, https://arxiv.org/abs/1905.00166.Google Scholar
• [31] Wolkowicz H, Saigal R, Vandenberghe L (2012) Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, vol. 27 (Springer, Boston).Google Scholar
• [32] Yannakakis M (1991) Expressing combinatorial optimization problems by linear programs. J. Comput. System Sci. 43(3):441–466.Crossref, Google Scholar