SDP / SOS Working Group Page

Schedule of Talks

Treasury of SDP / SOS Papers

Below are some of the papers that have appeared in our discussions. If you have any comments or suggestions for other papers, please email me at syildiz [at] email [dot] unc [dot] edu.

Papers from Alperen and Greg on 05/04/2017

• Relative Entropy Relaxations for Signomial Optimization - Chandrasekaran and Shah

Published: http://epubs.siam.org/doi/abs/10.1137/140988978

Public: https://arxiv.org/pdf/1409.7640.pdf

• A Positivstellensatz for Sums of Nonnegative Circuit Polynomials - Dressler, Iliman, and de Wolff

Public: https://arxiv.org/pdf/1607.06010.pdf

Papers on symmetry (circa 04/2017)

• Even symmetric sextics - Choi, Lam, and Reznick

Published: http://link.springer.com/article/10.1007%2FBF01166704

• Symmetries in semidefinite and polynomial optimization: relaxations, combinatorics, and the degree principle - Riener

Public: http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/22352

• Low Dimensional Test Sets for Nonnegativity of Even Symmetric Forms - Iliman and de Wolff

Public: https://arxiv.org/pdf/1303.4241.pdf

Papers from Alperen on 03/01/2017

• On the Newton Polytope of the Resultant - Sturmfels

Published (open access): http://www.emis.ams.org/journals/JACO/Volume3_2/m4496732732u7744.fulltext.pdf

• Tropical discriminants - Dickenstein, Feichtner, and Sturmfels

Public: https://arxiv.org/pdf/math/0510126.pdf

Papers mentioned on 02/13/2017

• Algebraic boundaries of Hilbert's SOS cones - Blekherman, Hauenstein, Ottem, Ranestad, and Sturmfels

Public: https://arxiv.org/pdf/1107.1846.pdf

• Dualities in Convex Algebraic Geometry - Rostalski and Sturmfels

Public: https://arxiv.org/pdf/1006.4894.pdf

• Algebraic Degree of Polynomial Optimization - Nie and Ranestad

Public: https://arxiv.org/pdf/0802.1233.pdf

Papers mentioned on 11/10/2016

Grothendieck's inequality on graphs

• Quadratic Forms on Graphs - Alon, Makarychev, Makarychev, and Naor

Public: http://konstantin.makarychev.net/pdf/qforms.pdf

Published: http://link.springer.com/article/10.1007/s00222-005-0465-9

• On Maximization of Quadratic Form Over Intersection of Ellipsoids with Common Center - Nemirovski, Roos, and Terlaky

Public: http://www2.isye.gatech.edu/~nemirovs/MP_QuadForms_1999.pdf

Published: http://link.springer.com/article/10.1007/s101070050100

Paper from Alperen on 10/27/2016

Hardness of approximation via LPs and SDPs

• Affine Reductions for LPs and SDPs - Braun, Pokutta, and Zink

Public: https://arxiv.org/pdf/1410.8816.pdf

Papers and a (short) book from Sercan on 10/13/2016

Unique Games Conjecture, Small-Set Expansion Hypothesis, and SOS certificates

• Sum-of-Squares Proofs and the Quest Toward Optimal Algorithms - Barak and Steurer

Public: https://arxiv.org/pdf/1404.5236v2.pdf

Related blog post: https://windowsontheory.org/2014/02/13/fun-and-games-with-sums-of-squares/

Related talk (video): https://www.newton.ac.uk/seminar/20130730150016002

• Hypercontractivity, Sum-of-Squares Proofs, and Their Applications - Barak et al.

Public (and extended): https://arxiv.org/pdf/1205.4484v3.pdf

Published: http://dl.acm.org/citation.cfm?doid=2213977.2214006

• On Khot's Unique Games Conjecture - Trevisan

Published (open access): http://www.ams.org/journals/bull/2012-49-01/S0273-0979-2011-01361-1/S0273-0979-2011-01361-1.pdf

Copositive programming

• Open Problems in the Theory of Copositive and Completely Positive Matrices - Berman, Dur, and Shaked-Monderer

Published (open access): http://repository.uwyo.edu/cgi/viewcontent.cgi?article=2943&context=ela

Distance geometry

• Open Research Areas in Distance Geometry - Liberti and Lavore

Public: https://arxiv.org/pdf/1610.00652v1.pdf

Approximation algorithms for optimization over "simple" sets

• Approximation Methods for Polynomial Optimization - Li, He, and Zhang

Published (book): link.springer.com/book/10.1007%2F978-1-4614-3984-4

Zhang and coauthors have a series of interesting papers on related problems, most of them published in the last decade. This book seems to present a unified treatment.

Exploiting sparsity in LP formulations for polynomial optimization

• LP formulations for mixed-integer polynomial optimization problems - Bienstock and Munoz

Public: https://arxiv.org/pdf/1501.00288v14.pdf

Paper and survey from Alperen on 09/30/2016

Exploiting sparsity in SDP and SOS

• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity - Waki, Kim, Kojima, and Muramatsu

Public: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.5279&rep=rep1&type=pdf

Published: http://epubs.siam.org/doi/abs/10.1137/050623802

• Exploiting Sparsity in SDP Relaxation of Polynomial Optimization Problems - Kim and Kojima

Public: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.640.2908&rep=rep1&type=pdf

Published: http://link.springer.com/chapter/10.1007/978-1-4614-0769-0_18

Paper from David on 09/09/2016

Approximation algorithms for optimization over the simplex

• An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex - de Klerk, Laurent, and Sun

Public: https://arxiv.org/pdf/1311.0173v3.pdf

Published: http://link.springer.com/article/10.1007/s10107-014-0825-6

Papers from Alperen on 09/08/2016

PSD and SOS properties on sparse supports

• Randomization, Sums of Squares, Near-Circuits, and Faster Real Root Counting - Bastani, Hillar, Popov, and Rojas

Public: http://www.math.tamu.edu/~rojas/s.pdf

• Amoebas, nonnegative polynomials and sums of squares supported on circuits - Iliman and de Wolff

Published (open access): https://resmathsci.springeropen.com/articles/10.1186/s40687-016-0052-2

Papers from Cynthia on 09/08/2016

Uniform denominators

• Uniform denominators in Hilbert's seventeenth problem - Reznick

Public: https://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/ReznickBruce/Reznick17.pdf

Published: http://link.springer.com/article/10.1007%2FBF02572604

• On the absence of uniform denominators in Hilbert's 17th problem - Reznick

Public: http://arxiv.org/pdf/math/0306163v1.pdf

Published: http://www.ams.org/journals/proc/2005-133-10/S0002-9939-05-07879-2/

Bounds for optimization over the sphere, hypercube, and related sets

• Certifying Random Polynomials Over the Unit Sphere via Sum-of-Squares Hierarchy - Bhattiprolu, Guruswami, and Lee

Public: http://arxiv.org/pdf/1605.00903v1.pdf

• Error Bounds for Some Semidefinite Programming Approaches to Polynomial Minimization on the Hypercube - de Klerk and Laurent

Public: http://www.optimization-online.org/DB_FILE/2010/04/2591.pdf

Published: http://epubs.siam.org/doi/abs/10.1137/100790835

• Symmetric Sums of Squares over k-Subset Hypercubes - Raymond, Saunderson, Singh, and Thomas

Public: http://arxiv.org/pdf/1606.05639.pdf

Slides from Sercan on 09/07/2016

Second-order cone representations of the cone of 3x3 PSD matrices

• Slides from the 4th SDP Days Workshop (2013) - Glineur, Saunderson, and Parrilo

Public: https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxzZHBkYXk0fGd4OjYzNzkyYjMzMTMwYWMzMjc

Papers from Greg on 08/25/2016

PSD and SOS properties on linear subspaces

• Positive semi-definiteness and sum-of-squares property of fourth order four dimensional Hankel tensors - Chen, Qi, and Wang

Public: https://arxiv.org/pdf/1502.04566v8.pdf

Published: http://www.sciencedirect.com/science/article/pii/S0377042716300668

• Dvoretzky Type Theorems for Multivariate Polynomials and Sections of Convex Bodies - Dol'nikov and Karasev

Public: https://arxiv.org/pdf/1009.0392v3.pdf

Published: http://link.springer.com/article/10.1007/s00039-011-0109-8

Reference from Alperen on 08/25/2016

Concentration of measure and Dvoretzky's Theorem

• Lecture notes of Keith Ball: http://library.msri.org/books/Book31/files/ball.pdf

Papers from David and Cynthia on 08/24/2016

Barrier functions for optimization

• Algebraic boundaries of Hilbert’s SOS cones - Blekherman et al.

Public: http://arxiv.org/pdf/1107.1846.pdf

Published: https://www.cambridge.org/core/journals/compositio-mathematica/article/algebraic-boundaries-of-hilberts-sos-cones/2C70CEE8CE1B2ED02B2D5762EC7F9DD5

• Discriminants and nonnegative polynomials - Nie

Public: http://math.ucsd.edu/~njw/PUBLICPAPERS/disnegpoly.pdf

Published: http://www.sciencedirect.com/science/article/pii/S0747717111001350

More tractable relaxations

• DSOS and SDSOS optimization: LP and SOCP-based alternatives to sum of squares optimization - Ahmadi and Majumdar

Published: http://ieeexplore.ieee.org/document/6814141/

• Sum of Squares Basis Pursuit with Linear and Second Order Cone Programming - Ahmadi and Hall

Public: http://arxiv.org/pdf/1510.01597.pdf

Uniform multipliers

• A Sum of Squares Approximation of Nonnegative Polynomials - Lasserre

Public: http://www.optimization-online.org/DB_FILE/2005/09/1217.pdf

Published: http://epubs.siam.org/doi/abs/10.1137/070693709

PSD and SOS properties on fixed supports

• Sums of squares and varieties of minimal degree - Blekherman, Smith, and Velasco

Public: http://arxiv.org/pdf/1308.0751.pdf

Published: http://www.ams.org/journals/jams/2016-29-03/S0894-0347-2015-00847-5/

Extension complexity

• The matching problem has no small symmetric SDP - Braun et al.

Public: http://arxiv.org/pdf/1504.00703v3.pdf

Published: http://dl.acm.org/citation.cfm?id=2884510

Related blog post: https://spokutta.wordpress.com/2012/06/22/on-the-polyhedral-inapproximability-of-the-sdp-cone/