Monique Laurent
Address       : CWI
                Science Park 123
	        1098 XG Amsterdam
	        The Netherlands
Postal address: CWI, Postbus 94079, 1090 GB Amsterdam
Phone         : +31 20 5924105 (office)
                +31 20 5929333 (reception)
                +31 20 5924189 (secretary)
Email         : monique at cwi dot nl
Office        : M238

how to reach CWI
Google map

Research group Networks and Optimization.

Since September 1, 2009, I am also affiliated as (part-time) full professor at the Department of Econometrics and Operations Research of Tilburg University.
Link to my CentER page.

See here for the research group seminar Combinatorics and Optimization

See here for the working group Algebra and Combinatorics.

Reading group on LP/SDP hierarchies.

Open positions:

Two PhD positions and one Postdoc position within the research project Approximation Algorithms, Quantum Information and Semidefinite Optimization, funded by an NWO-TOP grant, that I received in November 2013, in collaboration with Nikhil Bansal from the Department of Mathematics and Computer Science at the Technical University Eindhoven, and Ronald de Wolf from the research group Algorithms and Complexity.

Current teaching:

Fall 2014, LNMB PhD course - Networks and Semidefinite Programming, on Mondays, 10:15 - 12:00, at Utrecht University, from Monday 17 November 2014 until Monday 9 February 2015. Course website here.


MINO-COST Spring School on Optimization, Tilburg, March 10-13, 2015.

ISMP 2015, Pittsburgh, July 12-17, 2015.

Combinatorial Optimization - HIM, special trimester program, Bonn, Sepetember 1-December 18, 2015.
Rigidity Workshop, October 5-9, 2015.
Relaxation Workshop, November 16-20, 2015.
Game Theory Workshop, December 14-17, 2015.

Recent preprints

Bound-constrained polynomial optimization using only elementary calculations. With E. de Klerk, J. Lasserre and Z. Sun. Preprint at arXiv, July 2015.

A Lex-BFS-based recognition algorithm for Robinsonian matrices. With M. Seminaroti. Preprint at arXiv, May 2015.

On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings. With S. Burgdorf and T. Piovesan. Preprint at arXiv, February 2015.

Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization. With E. de Klerk and Z. Sun. Preprint at arXiv, November 2014.

An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution. With E. de Klerk and Z. Sun. Preprint at arXiv, July 2014.

Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone. With T. Piovesan. Preprint at arXiv, revised in April 2015.


Geometry of Cuts and Metrics (with M.M. Deza). Springer-Verlag, Berlin, 1997.
Russian translation, Moscow, 2001.
Softcover publication in 2010. See the book's flyer.
Book review in Optima 56 .
[Corrections can be found here.]


Optimization over polynomials: Selected topics. In Chapter 16 (Control Theory and Optimization) of Proceedings of the International Congress of Mathematicians 2014 (ICM 2014). Jang, S. Y., Kim, Y. R., Lee, D-W. & Yie, I. (eds.). Seoul: Kyung Moon SA Co. Ltd., p. 843-869, 2014. File here.

Copositive vs. moment hierarchies for stable sets. Discussion column, Optima 89, Mathematical Optimization Society Newsletter, 2012. Link here.

The Approach of Moments for Polynomial Equations. With P. Rostalski. Chapter 2 in Handbook on Semidefinite, Cone and Polynomial Optimization, M. Anjos and J.B. Lasserre (eds.), International Series in Operations Research & Management Science, 2012, Volume 166, Part 1, 25-60. Springer link and file (version, September 2010).

Semidefinite programming approximations for stable sets, colouring, and cuts in graphs. ps-file, January 2009, NVTI Newsletter.

Sums of squares, moment matrices and optimization over polynomials. In Emerging Applications of Algebraic Geometry, Vol. 149 of IMA Volumes in Mathematics and its Applications, M. Putinar and S. Sullivant (eds.), Springer, pages 157-270, 2009. File.
[Corrections can be found here.]
Updated version here, dated February 6, 2010.

Arbres et coupes de poids minimum. In Graphes et Applications 1, J.-C. Fournier (ed.), Hermes, Lavoisier, Paris, pages 225-261, 2007.

Semidefinite Programming and Integer Programming. With F. Rendl. In Handbook on Discrete Optimization, K. Aardal, G. Nemhauser, R. Weismantel (eds.), pages 393-514, Elsevier B.V., December 2005. File.

Matrix completion problems. In The Encyclopedia of Optimization, vol. III (Interior - M), pages 221-229. C.A. Floudas and P.M. Pardalos, editors, Kluwer, 2001. File.

Notes on Binary Spaces. Unpublished manuscript, 102 pages, 1998. File.

A tour d'horizon on positive semidefinite and Euclidean distance matrix completion problems. In P. Pardalos and H. Wolkowicz, editors, Topics in Semidefinite and Interior-Point Methods, volume 18 of The Fields Institute for Research in Mathematical Science, Communications Series. Providence, Rhode Island, pages 51--76, 1998.

Max-Cut Problem. Chapter in Annotated Bibliographies in Combinatorial Optimization, edited by M. Dell'Amico, F. Maffioli and S. Martello. John Wiley, pages 241-259, 1997.

Recent publications

New Limits on Fault-Tolerant Quantum Computation. With H. Buhrman, R. Cleve, N. Linden, A. Schrijver and F. Unger. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 411-419.

Semidefinite programming, moment matrices, combinatorial optimization, optimization over polynomials

A Lex-BFS-based recognition algorithm for Robinsonian matrices. Extended abstract. In Algorithms and Complexity: Proceedings of the 9th International Conference CIAC 2015, volume 9079 of Lecture Notes in Computer Science, pages 325-338. Springer- Verlag, 2015. File.

Entanglement-assisted zero-error source-channel coding. With J. Briet, H. Buhrman, T.Piovesan and G. Scarpa. IEEE Transactions on Information Theory, 61(2):1--15, 2015. Preprint at arXiv. (Extended abstract published at Eurocomb 2013.)

The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure. With M. Seminaroti. Operations Research Letters, 43(1):103--109, 2015. Preprint at arXiv:1407.2801v2.

An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex. With E. de Klerk and Z. Sun. Mathematical Programming Ser. B. Published online: 15 October 2014. Preprint at arXiv.

Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope. With M. E.-Nagy and A. Varvitsiotis, file, Journal of Combinatorial Theory B, 108:40-80, 2014.
(Revised version of the earlier preprint: On bounded rank positive semidefinite matrix completions of extreme partial correlation matrices. arXiv:1205.2040, 2012.)

Positive semidefinite matrix completion, universal rigidity and the Strong Arnold Property. With A. Varvitsiotis. arXiv:1301.6616, January 2013. Accepted for publication in Linear Algebra and its Applications.

Handelman 's hierarchy for the maximum stable set problem. With Zhao Sun. Journal of Global Optimization, 60(3):393-423, 2014. Preprint at arXiv:1305.7319.

Complexity of the positive semidefinite matrix completion problem with a rank constraint. With M. E.-Nagy and A. Varvitsiotis. In Discrete Geometry and Optimization, Volume 69 of Fields Institute Communications, K. Bezdek, A. Deza and Y. Ye (eds), Springer, pages 105--120, 2013. Preprint at arXiv:1203.6602.

A new graph parameter related to bounded rank positive semidefinite matric completions. With A. Varvitsiotis. Mathematical Programming, Ser. A., Volume 145, Issue 1-2, pp 291-325, June 2014. Preprint at arXiv:1204.0734.

Moment matrices, border bases and radical computation. With J.B. Lasserre, B. Mourrain, Ph. Rostalski and Ph. Trebuchet. Journal of Symbolic Computation, 51, 63-85, 2013. Preprint at arXiv:1112.3197.

The Gram dimension of a graph. With A. Varvitsiotis. In Proceedings of the 2nd International Symposium on Combinatorial Optimization. A.R. Mahjoub et a. (Eds.): ISCO 2012, LCS 7422, pp. 356--367, 2012. Preprint at arXiv:1112.5960.

A new semidefinite programming relaxation for cycles in binary matroids and cuts in graphs. With J. Gouveia, P. Parrilo and R. Thomas. Mathematical Programming, 112(1-2), 203-225, 2012. arXiv:0907.4518.

Computing the Grothendieck constant of some graph classes. With A. Varvitsiotis. Operations Research Letters, Volume 39, Issue 6, November 2011, Pages 452-456. Preprint.

On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems. With E. de Klerk. SIAM Journal on Optimization, 21, 824-832, 2011. File.

On Leonid Gurvits's proof for permanents. With A. Schrijver. The American Mathematical Monthly, 117(10): 903-911, 2010. File.

Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube. With E. de Klerk. SIAM Journal on Optimization, 20(6):3104-3120, 2010. File

A generalized flat extension theorem for moment matrices. With B. Mourrain. Archiv der Mathematik, 93(1):87--98, July 2009. File.

A prolongation-projection algorithm for computing the finite real variety of an ideal. With J. Lasserre and P. Rostalski, Theoretical Computer Science 410(27-29):2685-2700, 2009. File.

Block-diagonal semidefinite programming hierarchies for 0/1 programming. With N. Gvozdenovic and F. Vallentin. Operations Research Letters 37:27-31, 2009. File.

A unified approach to computing real and complex zeros of zero-dimensional ideals. with J.B. Lasserre and P. Rostalski. In Emerging Applications of Algebraic Geometry, Vol. 149 of IMA Volumes in Mathematics and its Applications, M. Putinar and S. Sullivant (eds.), Springer, pages 125-155, 2009. File.

Semidefinite Programming in Combinatorial and Polynomial Optimization. Nieuw Archief voor Wiskunde, NAW 5/9 nr. 4, December 2008. File.

The operator $\Psi$ for the Chromatic Number of a Graph. With N. Gvozdenovic. SIAM Journal on Optimization 19(2):572-591, 2008. File.

Computing semidefinite programming lower bounds for the (fractional) chromatic number via block-diagonalization. With N. Gvozdenovic. SIAM Journal on Optimization 19(2):592-615, 2008. File.

Computing the real variety of an ideal - A real algebraic and symbolicnumeric algorithm. With J.-B. Lasserre and P. Rostalski. In SAC'08: Proceedings of the 2008 ACM Symposium on Applied Computing, pages 1845--1846, Fortaleza, Brazil, 2008.

Semidefinite characterization and computation of zero-dimensional real radical ideals, with J.-B. Lasserre and P. Rostalski. Foundations of Computational Mathematics, 8(5):607--647, 2008. Link.

Semidefinite representations for finite varieties. Mathematical Programming, 109:1--26, 2007. File.

Strengthened semidefinite programming bounds for codes. Mathematical Programming, 109(2-3):239-261, 2007.

A PTAS for the minimization of polynomials of fixed degree over the simplex. With E. De Klerk and P. Parrilo. Theoretical Computer Science, 361(2-3):210--225, 2006. (Link to TCS here.)

Semidefinite approximations for global unconstrained polynomial optimization. With Dorina Jibetean. SIAM Journal on Optimization 16(2) 490--514, 2005. File.

Semidefinite bounds for the stability number of a graph via sums of squares of polynomials. With N. Gvozdenovic. Mathematical Programming, 110(1):145--173, 2007. (Extended abstract in Lecture Notes in Computer Science, vol 3509/2005, pages 136-151. Integer Programming and Combinatorial Optimization: 11th International IPCO Conference, Berlin, June 8-10, 2005.)

On the equivalence of algebraic approaches to the minimization of forms on the simplex. With E. de Klerk and P. Parrilo. In Positive Polynomials in Control, D. Henrion and A. Garulli, eds., Lecture Notes on Control and Information Sciences, Vol. 312, pages 121-133, Springer Verlag, Berlin, 2005. Paper here.

Revisiting two theorems of Curto and Fialkow on moment matrices. Proceedings of the American Mathematical Society 133, no. 10, 2965-2976, 2005.

Semidefinite relaxations for Max-Cut. In The Sharpest Cut: The Impact of Manfred Padberg and His Work. M. Gr\"otschel, ed., pages 257-290, MPS-SIAM Series in Optimization 4, 2004.

Lower bound for the number of iterations in semidefinite relaxations for the cut polytope. Mathematics of Operations Research, 28(4):871--883, 2003.

A comparison of the Sherali-Adams, Lov\'asz-Schrijver and Lasserre relaxations for 0-1 programming. Mathematics of Operations Research, 28(3):470-496, 2003.

Tighter linear and semidefinite relaxations for max-cut based on the Lov\'asz-Schrijver lift-and-project procedure. SIAM Journal on Optimization, 12:345--375, 2001.

Connections between semidefinite relaxations of the max-cut and stable set problems (with S. Poljak and F. Rendl). Mathematical Programming, 77:225-246, 1997.

On the facial structure of the set of correlation matrices (with S. Poljak). SIAM Journal on Matrix Analysis, 17:530--547, 1996.

Gap inequalities for the cut polytope (with S. Poljak). European Journal of Combinatorics, 17:233--254, 1996.

On a positive semidefinite relaxation of the cut polytope (with S. Poljak). Linear Algebra and its Applications, 223/224:439--461, 1995.

Matrix completion

On the sparsity order of a graph and its deficiency in chordality. Combinatorica, 21:543-570, 2001.

Polynomial instances of the positive semidefinite and euclidean distance matrix completion problems. SIAM Journal on Matrix Analysis and its Applications, 22:874-894, 2000.

A connection between positive semidefinite and Euclidean distance matrix completion problems. Linear Algebra and its Applications, 273:9--22, 1998.

Cuts, matrix completions and graph rigidity. Mathematical Programming, 79:255--283, 1997.

The real positive semidefinite completion problem for series-parallel graphs. Linear Algebra and its Applications, 252:347--366, 1997.

Metric spaces (the equidistant problem)

Equilateral dimension of the rectilinear space. With J. Koolen and A. Schrijver. Designs, Codes and Cryptography, 21, 149--164, 2000.

Embedding into rectilinear spaces (with H.-J. Bandelt and V. Chepoi). Discrete and Computational Geometry, 19:595--604, 1998.

Cycles in binary matroids

Cycle bases for lattices of binary matroids with no Fano dual minor and their one-element extensions. With T. Fleiner, W. Hochst\"attler and M. Loebl. Journal of Combinatorial Theory B 77:25--38, 1999.

A characterization of box $1/d$-integral binary clutters (with A.M.H. Gerards). Journal of Combinatorial Theory B, 65:186--207, 1995.

Graph parameters

A minor-monotone graph invariant based on oriented matroids (with J. Edmonds and A. Schrijver). Discrete Mathematics, 165/166:219--226, 1997.

On a minor-monotone graph invariant (with H. van der Holst and A. Schrijver). Journal of Combinatorial Theory B, 65:291--304, 1995.

Hypermetric spaces and geometry of numbers

Delaunay transformations of Delaunay polytopes. Journal of Algebraic Combinatorics, 5:37--46, 1996.

Hypermetrics in geometry of numbers (with M. Deza and V.P. Grishukhin). In L. Lov\'asz W. Cook and P. Seymour, editors, Combinatorial Optimization, volume 20 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, pages 1--109, 1995.

The hypermetric cone is polyhedral (with M. Deza and V.P. Grishukhin). Combinatorica, 13:1--15, 1993.

Extreme hypermetrics and $L$-polytopes (with M. Deza and V.P. Grishukhin). In G. Halasz et al., editor, Sets, Graphs and Numbers, volume 60 of Colloquia Mathematica Societatis Janos Bolyai, pages 157--209, 1992.

Some slides of talks

Semidefinite programming characterization and computation of real radical ideals at MEGA, Stockholm, May 30-June 3, 2011.

Optimization over polynomials with sums of squares and moment matrices at Positivity, Valuations and Quadratic Forms, Konstanz, October 1-6, 2009.

Computing real radical ideals and real roots of polynomial equations with semidefinite programming at Convex Algebraic geometry, Optimization, and Applications, AIM, Palo Alto, September 21-25, 2009.

Semidefinite programming bounds for stable sets and coloring at Combinatorial Optimization, Oberwolfach, November 10-14, 2008.

Real solving polynomial equations with semidefinite programming at LAW 2008, Kranjska Gora, Slovenia, May 27-June 5, 2008.

Three lectures on Moment Matrices and Optimization over Polynomials as part of the ADONET Doctoral school on Optimization over Polynomials and Semidefinite Programming organized at the University of Klagenfurt, September 12-16, 2005.
1. Moment Matrices and Optimization over Polynomials - General Introduction
2. Algebraic Preliminaries and Results about Moment Matrices
3. Unconstrained Polynomial Optimization

Lecture on Semidefinite Programming in Polynomial Optimization at the SIAM Conference on Optimization, Stockholm, May 15-19, 2005. (More compact set of slides here.)

Five lectures on Semidefinite programming and combinatorial optimization, as part of a series of doctoral courses in Discrete Optimization, organized at CORE, Louvain La Neuve,
September 1-12, 2003.
1. A Journey from some classic polyhedral results to the Goemans-Williamson approximation algorithm for Max-Cut.
2. The maximum stable set problem: Basic polyhedral results and the Theta function.
3. Lift-and-Project methods for 0/1 programming.
4. Polynomial optimization and sums of squares of polynomials.
5. Approximating the stability number of a graph via copositive programming - Approximating forms over the simplex - Polya's theorem.

Conference Geometric Convex Combinatorics, Oberwolfach, 16-22 June, 2002. Semidefinite relaxations for 0-1 polytopes - Application to Max-Cut.

Conference HPOPT, Utrecht, 6-8 June 2001. Cut, lift, and project methods for 0-1 programming.

Editorial work

Associate editor, SIAM Journal on Optimization (since 2001).

Associate editor, Mathematics of Operations Research (since 2001).

Associate editor, SIAM Journal on Discrete Mathematics (since 2007).

Associate editor, Mathematical Programming, Series A (since 2012).

Associate editor, Journal of Mathematical Analysis and its Applications (2006-2009).

Editorial board of the MPS-SIAM book Series on Optimization (2003-2007).

(Co)-organization of workshops

4th SDP Days, CWI, Amsterdam, March 21, 22, 2013.

Thematic programme on Polynomial Optimisation at the Isaac Newton Institute for Mathematical Sciences, Cambridge UK, 15 July - 9 August 2013.

Workshop on Geometry and Algebra of Linear Matrix Inequalities, Centre International de Rencontres Mathematiques (CIRM), November 12-16, 2013.

Thematic programme Inverse Moment Problems: the Crossroads of Analysis, Algebra, Discrete Geometry and Combinatorics, IMS-NUS, Singapore, November 2013 - January 2014.

MFO Workshop on Combinatorial Optimization, Oberwolfach, November 14--19, 2011.

CWI Workshop Day on Applications of Semidefinite Programming, July 1, 2011.
Additional lectures on Thursday June 30.

CWI Symposium Day on Large-Scale and Uncertain Optimization, November 12, 2010.

IPAM trimester program: Modern Trends in Optimization and Its Application, UCLA, September 13-December 17, 2010.

Oberwolfach seminar on Semidefinite Optimization: Theory, Algorithms and Applications, Oberwolfach, May 23-29, 2010. With lectures by S. Arora, M. Laurent, P. Parrilo, F. Rendl and F. Vallentin. Details can be found here.

EIDMA minicourse on Algebraic Optimization and Semidefinite Programming by Prof. Pablo Parrilo (MIT), CWI, May 31 - June 4, 2010. Registration is open till May 6, 2010. Details about the venue at CWI here.

HPOPT 2010 - 11th International Workshop on High Performance Optimization Techniques - Advances in Semidefinite Programming, University of Tilburg, June 14 - 16, 2010.

CWI seminar day, Applications of semidefinite programming, CWI, Amsterdam, December 3, 2009.

Oberwolfach seminar, New Trends in Algorithms for Real Algebraic Geometry, MFO, Oberwolfach, November 22-28, 2009. With lectures by S. Basu, M. Laurent, M.-F. Roy, and F. Sottile; details at the Oberwolfch homepage.
My lectures are based on the survey article Sums of Squares, Moment Matrices and Optimization over Polynomials, posted above. The slides for my first lecture are posted here.

DIAMANT seminar day: Applications of semidefinite programming, CWI, Amsterdam, March 13, 2009.

Minisymposium: Algebra in Optimization at 5th ECM, Amsterdam, July 14-18, 2008.

HPOPT 2008 - 10th International Workshop on High Performance Optimization Techniques, Tilburg, June 11-13, 2008, on Algebraic Structure in Semidefinite Programming, with a tutorial day on June 11 on Using Symmetry in Semidefinite Programming.

DIAMANT Intercity seminar on Algebra and Symmetries in Combinatorics and Optimization, University of Amsterdam, June 30, 2006.

ADONET Doctoral school on Optimization over Polynomials and Semidefinite Programming, University of Klagenfurt, September 12-16, 2005.

HPOPT 2004, dedicated to the memory of Jos Sturm: 8th International Workshop on High Performance Optimization Techniques, CWI, Amsterdam, June 23-25, 2004, on Optimization and Polynomials, including a tutorial day on Sums of Squares in Optimization.

Recent events

Workshop Emerging Developments in Real Algebraic Geometry: Positivity, Convexity, NC-Geometry, Optimization , Magdeburg, February 20-24, 2012.

Workshop HPOPT 2012: Algorithmic convexity and applications, Delft, June 20-22, 2012.

ISMP 2012: 21st International Symposium on Mathematical Programming, Berlin, August 19-24, 2012.

MAP 2012: Mathematics, Algorithms and Proofs, Konstanz, September 17--21, 2012.

Workshop on Large Scale Conic Optimization, within the thematic programme Optimization: Computation, Theory and Modeling at IMS-NUS, Singapore, November 19-23, 2012.

Recent teaching

Spring 2014, Mastermath course on Semidefinite Optimization on Tuesdays, 10:15-13:00, at BBL169 (Buys Ballotbuilding) in Utrecht University. (From Feb. 4 till May 13 2014.)

Fall 2012, LNMB course Networks and Semidefinite Programming on Mondays, 10h15-12h00, Utrecht University, Mathematical Building, room 611AB.

Spring 2012, Mastermath Course on Semidefinite Optimization on Tuesdays, UvA C1.112, 10h45 - 13h00.

Some interesting links

MINO, Initial Training Network Mixed Integer Nonlinear Optimization, from 2013.

DIAMANT , Discrete, Interactive and Algorithmic Mathematics, Algebra and Number Theory [dutch mathematics cluster funded by NWO, OCW and EZ]

ADONET , Algorithmic Discrete Optimization Network [EU Marie Curie Research Training Network]

RAAG, Real Algebraic and Analytic Geometry Network [EU Research and Training Network]

Semidefinite programming

Mathematical Optimization Society

List of publications on MathSciNet

Click on the Help button to see what you can do with this OutBox page.