A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs (2009)
Gouveia, João, Laurent, Monique, Parrilo, Pablo A., Thomas, Rekha
The theta bodies of a polynomial ideal are a series of semidefinite programming relaxations of the convex hull of the real variety of the ideal. In this paper we construct the theta bodies of the...
A UNIFIED APPROACH TO COMPUTING REAL AND COMPLEX ZEROS OF ZERO-DIMENSIONAL IDEALS (2009)
Jean Bernard Lasserre, Monique Laurent
Abstract. In this paper we propose a unified methodology for computing the set VK(I) of complex (K = C) or real (K = R) roots of an ideal I ⊆ R[x], assuming VK(I) is finite. We show how moment...
Sums of squares, moment matrices and optimization over polynomials, preprint 2007 (2009)
Abstract. We consider the problem of minimizing a polynomial over a semialgebraic set defined by polynomial equations and inequalities, which is NP-hard in general. Hierarchies of semidefinite...
A Sparse Flat Extension Theorem for Moment Matrices (2009)
Laurent, Monique, Mourrain, Bernard
In this note we prove a generalization of the flat extension theorem of Curto and Fialkow for truncated moment matrices. It applies to moment matrices indexed by an arbitrary set of monomials and its...
A Sparse Flat Extension Theorem for Moment Matrices (2009)
Laurent, Monique, Mourrain, Bernard
In this note we prove a generalization of the flat extension theorem of Curto and Fialkow for truncated moment matrices. It applies to moment matrices indexed by an arbitrary set of monomials and its...
A Sparse Flat Extension Theorem for Moment Matrices (2008)
Laurent, Monique, Mourrain, Bernard
In this note we prove a generalization of the flat extension theorem of Curto and Fialkow for truncated moment matrices. It applies to moment matrices indexed by an arbitrary set of monomials and its...
A Sparse Flat Extension Theorem for Moment Matrices (2008)
Laurent, Monique, Mourrain, Bernard
In this note we prove a generalization of the flat extension theorem of Curto and Fialkow for truncated moment matrices. It applies to moment matrices indexed by an arbitrary set of monomials and its...
A Sparse Flat Extension Theorem for Moment Matrices (2008)
Laurent, Monique, Mourrain, Bernard
In this note we prove a generalization of the flat extension theorem of Curto and Fialkow for truncated moment matrices. It applies to moment matrices indexed by an arbitrary set of monomials and its...
BLOCK-DIAGONAL SEMIDEFINITE PROGRAMMING HIERARCHIES FOR 0/1 PROGRAMMING (2008)
Monique Laurent, Frank Vallentin
Abstract. Lovász and Schrijver, and later Lasserre, proposed hierarchies of semidefinite programming relaxations for general 0/1 linear programming problems. In this paper these two constructions...
Hierarchies of semidefinite relaxations for 0/1 polytopes have been constructed by Lasserre (2001a) and by Lovász and Schrijver (1991). The cut polytope of a graph on n nodes can be expressed as a...
New Limits on Fault-Tolerant Quantum Computation Harry Buhrman* (2008)
Monique Laurent, Alexander Schrijver
Abstract We show that quantum circuits cannot be made fault-tolerant against a depolarizing noise level of ^ ` = (6-2p2) /7 ss 45%, thereby improving on a previous boundof 50 % (due to Razborov...
Semidefinite Programming and Integer Programming (2008)
We survey how semidefinite programming can be used for finding good approximative solutions to hard combinatorial optimization problems.
Bert Gerards, Bert Gerards, Monique Laurent, Monique Laurent
Abstract. Let Q 6 denote the port of the dual Fano matroid F 7 and let Q 7 denote the clutter consisting of the circuits of the Fano matroid F 7 that contain a given element. Let L be a binary...
LIENS Ecole Normale Sup'erieure (2007)
Monique Laurent, Monique Laurent, Svatopluk Poljak, Svatopluk Poljak
On a positive semidefinite relaxation of the cut polytope
The Hilbert Basis of the Cut Cone over the Complete Graph on Six Vertices (2007)
Fran Cois, Michel Deza, Monique Laurent
Let C be a real polyhedral cone, generated by the integer vectors x 1 ; : : : ; x n . The set of points of this cone with integer coordinates forms a semi-group whose minimal set of generators (for...
One-Third-Integrality in the Max-Cut Problem (2007)
Monique Laurent, Svatopluk Poljak
. Given a graph G = (V; E), the metric polytope S(G) is defined by the inequalities x(F ) \Gamma x(C n F ) jF j \Gamma 1 for F ` C; jF j odd ; C cycle of G, and 0 x e 1 for e 2 E. Optimization over...
Lower Bound for the Number of Iterations in Semidenite Hierarchies for the Cut Polytope (2007)
Hierarchies of semidenite relaxations for 0=1 polytopes have been constructed by Lasserre (2001a) and by Lovasz and Schrijver (1991), permitting to nd the cut polytope of a graph on n nodes in n...
On the Sparsity Order of a Graph and its Deficiency in Chordality (2007)
Given a graph G on n nodes, let PG denote the cone consisting of the positive semidefinite n \Theta n matrices (with real or complex entries) having a zero entry at every off-diagonal position...
. X is said to be a Hilbert base if every vector (2007)
Monique Laurent, Monique Laurent, In R
Let X be a set of vectors in R m
On the Order of a Graph and its (2007)
M. Laurent, Mathematisch Centrum (smc, The Dutch Foundation, Monique Laurent
and their applications. SMC is sponsored by the Netherlands Organization for Scientific Research (NWO). CWI is a member of
A PTAS for the Minimization of Polynomials of Fixed Degree over the Simplex (2007)
Etienne De Klerk, Monique Laurent, Pablo Parrilo
We consider the problem of computing the minimum value p min taken by a polynomial p(x) of degree d over the standard simplex Δ. This is an NP-hard problem already for degree d = 2. For any...
A PTAS for the minimization of polynomials of fixed degree over the simplex - Extended (2007)
Etienne De Klerk, Monique Laurent, Pablo Parrilo
this paper we show that problem (1) has a polynomial approximation scheme (PTAS) when restricted to the class of polynomials having a fixed degree 2. Given an integer k 1, let #(k) := kx } denote the...
A PTAS for the Minimization of Polynomials of Fixed Degree over the Simplex (2007)
Etienne De Klerk, Monique Laurent, Pablo Parrilo
We consider the problem of computing the minimum value p min taken by a polynomial p(x) of degree d over the standard simplex #. This is an NP-hard problem already for degree d = 2. For any integer k...
A UNIFIED APPROACH TO COMPUTING REAL AND COMPLEX ZEROS OF ZERO-DIMENSIONAL IDEALS (2007)
Jean Bernard Lasserre, Monique Laurent
Abstract. In this paper we propose a unified methodology for computing the set VK(I) of complex (K = C) or real (K = R) roots of an ideal I ⊆ R[x], assuming VK(I) is finite. We show how moment...
New Limits on Fault-Tolerant Quantum Computation (2006)
Buhrman, Harry, Cleve, Richard, Laurent, Monique, Linden, Noah, Schrijver, Alexander, Unger, Falk
We show that quantum circuits cannot be made fault-tolerant against a depolarizing noise level of approximately 45%, thereby improving on a previous bound of 50% (due to Razborov). Our precise...
New limits on fault-tolerant quantum computation (2006)
Harry Buhrman, Monique Laurent, Noah Linden, Alexander Schrijver
Semidefinite approximation for global unconstrained polynomial optimization (2005)
Dorina Jibetean, Monique Laurent
Abstract. We consider the problem of minimizing a polynomial function on R n, known to be hard even for degree 4 polynomials. Therefore approximation algorithms are of interest. Lasserre
Revisiting Two Theorems of Curto and Fialkow on Moment Matrices (2004)
We revisit two results of Curto and Fialkow on moment matrices. The first result asserts that every sequence...
Semidefinite Representations for Finite Varieties (2004)
We consider the problem of minimizing a polynomial over a set defined by polynomial equations and inequalities. When the polynomial equations have a finite set of complex solutions, we can...
Converging Semidefinite Bounds for Global Unconstrained Polynomial Optimization (2004)
Dorina Jibetean, Monique Laurent
We consider here the problem of minimizing a polynomial function on R . The problem is known to be hard even for degree 4. Therefore approximation algorithms are of interest. Lasserre [11] and...
Revisiting two theorems of Curto and Fialkow on moment matrices (2004)
We revisit two results of Curto and Fialkow on moment matrices. The first result asserts that every sequence y ∈ R Zn + whose moment matrix M(y) is positive semidefinite and has finite rank r is...
Semidefinite Representations for Finite Varieties (2003)
We present a concise semidefinite formulation for the problem of minimizing a polynomial over a semi-algebraic set defined by polynomial equalities and inequalities.
On the Equivalence of Algebraic Approaches to the Minimization of Forms on the Simplex (2003)
Etienne De Klerk, Monique Laurent, Pablo Parrilo
We consider the problem of minimizing a form on the standard simplex [equivalently, the problem of minimizing an even form on the unit sphere]. Converging hierarchies of approximations for this...
Semidefinite representations for finite varieties (2002)
We consider the problem of minimizing a polynomial over a semi-algebraic set defined by polynomial equalities and inequalities. When the polynomial equalities have a finite number of complex...
Semidefinite Relaxations for Max-Cut (2002)
We compare several semidefinite relaxations for the cut polytope obtained by applying the lift and project methods of Lovász and Schrijver and of Lasserre. We show that the tightest relaxation is...
Matrix completion problems (2001)
Matrix completion problems are concerned with determining whether partially specified matrices can be completed to fully specified matrices satisfying certain prescribed properties. In this article...
Semidefinite relaxations for Max-Cut (2001)
ABSTRACT. We compare several semidefinite relaxations for the cut polytope obtained by applying the lift and project methods of Lov'asz and Schrijver and of Lasserre. We show that the tightest...
Sherali and Adams [SA90], Lov'asz and Schrijver [LS91] and, recently, Lasserre [Las01b] have proposed lift and project methods for constructing hierarchies of successive linear or semidefinite...
A Comparison of the Sherali-Adams, Lovasz-Schrijver and Lasserre Relaxations for 0 (2001)
Programming Monique Laurent, Monique Laurent
Sherali and Adams (1990), Lovasz and Schrijver (1991) and, recently, Lasserre (2001) have constructed hierarchies of successive linear or semidefinite relaxations of a 0 1 polytope P converging to P...
and Lasserre Relaxations for 0 − 1 Programming (2001)
A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre
Abstract. Given an undirected graph G = (V; E) with node set V = [1; n], a subset S ` V and a rational vector a 2 Q S[E, the positive semidefinite matrix completion problem consists of determining...
Equilateral dimension of the rectilinear space (1999)
Jack Koolen, Monique Laurent, Er Schrijver
Dedicated to J.J. Seidel on the occasion of his 80th birthday. It is conjectured that there exist at most 2k equidistant points in the k-dimensional rectilinear space. This conjecture has been...
Tamas Fleiner, Winfried Hochstattler, Winfried Hochstattler, Monique Laurent, Martin Loebl
In this paper we study the question of existence of a cycle basis (that is, a basis consisting only of cycles) for the lattice Z(M) generated by the cycles of a binary matroid M. We show that, if M...
Cycle bases for lattices of matroids with no Fano dual minor and their one-element extensions (1996)
W. Hochstattler, M. Laurent, Martin Loebl, Zentrum Paralleles, Rechnen Liens, Ecole Normale Sup'erieure, ...
In this paper we study the question of existence of a basis consisting only of cycles for the lattice Z(M) generated by the cycles of a binary matroid M. We show that, if M has no Fano dual minor,...
Gap Inequalities for the Cut Polytope (1996)
Monique Laurent, Svatopluk Poljak
We introduce a new class of inequalities valid for the cut polytope, which we call gap inequalities. Each gap inequality is given by a finite sequence of integers, whose "gap" is defined as...
The Hilbert Basis of the Cut Cone over the Complete Graph on Six Vertices (1995)
François Laburthe, Michel Deza, Monique Laurent
Let C be a real polyhedral cone, generated by the integer vectors x 1 ; : : : ; x n . The set of points of this cone with integer coordinates forms a semi-group whose minimal set of generators (for...
On the Facial Structure of the Set of Correlation Matrices (1995)
Monique Laurent, Svatopluk Poljak
We study the facial structure of the set E n\Thetan of correlation matrices (i.e., the positive semidefinite matrices with diagonal entries equal to 1). In particular, we determine the possible...
Connections Between Semidefinite Relaxations of the Max-Cut and Stable Set Problems (1995)
Monique Laurent, Svatopluk Poljak, Franz Rendl
We describe the links existing between a recently introduced semidefinite relaxation for the max-cut problem and the well known semidefinite relaxation for the stable set problem underlying the...
Hypercube Embeddings and Designs (1994)
Hypercube Embeddings, Michel Deza, Michel Deza, Monique Laurent, Monique Laurent
This is a survey on hypercube embeddable semimetrics and the link with designs. We investigate, in particular, the variety of hypercube embeddings of the equidistant metric. For some parameters, it...
In this paper, we survey the metric properties of isometric subgraphs of hypercubes and, more generally, of ` 1 -graphs. An ` 1 -graph is a graph which is hypercube embeddable, up to scale. In...
Measure aspects of cut polyhedra: l_1-embeddability and Probability (1993)
Michel Deza, Michel Deza, Monique Laurent, Monique Laurent
26.62> L 1 -metric 8.1 The L 1 -metric in probability theory 8.2 The ` 1 -metric in statistical data analysis 8.3 The ` 1 -metric in computer vision and pattern recognition 2 M. Deza and M....
On a Positive Semidefinite Relaxation of the Cut Polytope (1993)
Monique Laurent, Svatopluk Poljak
We study the convex set Ln defined by Ln := fX j X = (x ij ) positive semidefinite n \Theta n matrix; x ii = 1 for all ig: We describe several geometric properties of Ln . In particular, we show that...
Hypercube Embedding of Distances with Few Values (1993)
Monique Laurent, Monique Laurent
A distance d on a finite set V is hypercube embeddable if it can be isometrically embedded into the hypercube f0; 1g m for some m 1, i.e., if the elements i 2 V can be labeled by sets A i in such a...
Applications of Cut Polyhedra (1992)
Michel Deza, Monique Laurent, M. Deza, M. Laurent, M. Laurent
We group in this paper, within a unified framework, many applications of the following polyhedra: cut, boolean quadric, hypermetric and metric polyhedra. We treat, in particular, the following...
Characterization of the 5'-flanking region for the human fibrinogen {beta} gene (1987)
Huber, Philippe, Dalmon, Jacques, Courtois, Gilles, Laurent, Monique, Assouline, Zahra, Marguerie, Gérard
To identify the possible regulatory sequences in the genetic expression of fibrinogen, a human genomic DNA library raised in λEHBL 4 phage was screened using cDNA probes coding for the Aα, Bβ and...
Le catalogue de la bibliothèque du Séminaire de Québec, 1782 /--par Monique Laurent. (1973)
Thèse (D.E.S.)--Université Laval, 1973.
Le catalogue de la bibliothèque du Séminaire de Québec, 1782 [microforme] / (1973)
Thèse (D.E.S.)--Université Laval, 1973.
Le catalogue de la bibliothèque du Séminaire de Québec, 1782 / (1973)
Thèse (D.E.S.)--Université Laval, 1973.
Le catalogue de la bibliothèque du Séminaire de Québec, 1782 / (1973)
Thèse (de D.E.S.) - Université Laval, 1973.
Le catalogue de la bibliothèque du Séminaire de Québec, 1782 [microforme] / (1973)
Thèse - Université Laval.
Thesis (doctoral)--Grenoble, 1971.
La correspondance de l'abbé Louis Beaudet, 1853-1858 / (1965)
Thèse (de licence) - Université Laval, 1965.
Electron Microscopy of Kinetoplastic DNA from Trypanosoma mega
Laurent, Monique, Steinert, M.
The electron microscopical aspect of kinetoplast DNA has been studied in preparations obtained by osmotic disruption of isolated organelles. A large amount of this DNA appears to be of large...
Electron Microscopy of Kinetoplastic DNA from Trypanosoma mega
Laurent, Monique, Steinert, M.
The electron microscopical aspect of kinetoplast DNA has been studied in preparations obtained by osmotic disruption of isolated organelles. A large amount of this DNA appears to be of large...