
In this paper we consider a parametric family of quadratically constrained
quadratic programs (QCQP) and their associated semidefinite programming (SDP)
relaxations. Given a value of the parameters at which the SDP relaxation is
exact, we study conditions (and quantitative bounds) under which the relaxation
will continue to be exact as the parameter moves in a neighborhood around it.
More generally, our results can be used to analyze SDP relaxations of
polynomial optimization problems. Our framework captures several estimation
problems such as low rank approximation, camera triangulation, rotation
synchronization and approximate matrix completion. The SDP relaxation correctly
solves these problems under noiseless observations, and our results guarantee
that the relaxation will continue to solve them in the low noise regime.

In this paper we introduce a natural model for the realization space of a
polytope up to projective equivalence which we call the slack realization space
of the polytope. The model arises from the positive part of an algebraic
variety determined by the slack ideal of the polytope. This is a saturated
determinantal ideal that encodes the combinatorics of the polytope. We also
derive a new model of the realization space of a polytope from the positive
part of the variety of a related ideal. The slack ideal offers an effective
computational framework for several classical questions about polytopes such as
rational realizability, nonprescribability of faces, and realizability of
combinatorial polytopes.

Efficient representations of convex sets are of crucial importance for many
algorithms that work with them. It is wellknown that sometimes, a complicated
convex set can be expressed as the projection of a much simpler set in higher
dimensions called a lift of the original set. This is a brief survey of recent
developments in the topic of lifts of convex sets. Our focus will be on lifts
that arise from affine slices of real positive semidefinite cones known as psd
or spectrahedral lifts. The main result is that projection representations of a
convex set are controlled by factorizations, through closed convex cones, of an
operator that comes from the convex set. This leads to several research
directions and results that lie at the intersection of convex geometry,
combinatorics, real algebraic geometry, optimization, computer science and
more.

Tur\'an problems in extremal combinatorics ask to find asymptotic bounds on
the edge densities of graphs and hypergraphs that avoid specified subgraphs.
The theory of flag algebras proposed by Razborov provides powerful methods
based on semidefinite programming to find sums of squares that establish edge
density inequalities in Tur\'an problems. Working with polynomial analogs of
the flag algebra entities, we prove that such sums of squares created by flag
algebras can be retrieved from a restricted version of the symmetryadapted
semidefinite program proposed by Gatermann and Parrilo. This involves using the
representation theory of the symmetric group for finding succinct sums of
squares expressions for invariant polynomials. The connection reveals several
combinatorial and structural properties of flag algebra sums of squares, and
offers new tools for Tur\'an and other related problems.

We consider the problem of finding sum of squares (sos) expressions to
establish the nonnegativity of a symmetric polynomial over a discrete
hypercube whose coordinates are indexed by the $k$element subsets of $[n]$.
For simplicity, we focus on the case $k=2$, but our results extend naturally to
all values of $k \geq 2$. We develop a variant of the GatermannParrilo
symmetryreduction method tailored to our setting that allows for several
simplifications and a connection to flag algebras.
We show that every symmetric polynomial that has a sos expression of a fixed
degree also has a succinct sos expression whose size depends only on the degree
and not on the number of variables. Our method bypasses much of the technical
difficulties needed to apply the GatermannParrilo method, and offers
flexibility in obtaining succinct sos expressions that are combinatorially
meaningful. As a byproduct of our results, we arrive at a natural
representationtheoretic justification for the concept of flags as introduced
by Razborov in his flag algebra calculus. Furthermore, this connection exposes
a family of nonnegative polynomials that cannot be certified with any fixed
set of flags, answering a question of Razborov in the context of our finite
setting.

The positive semidefinite (psd) rank of a polytope is the size of the
smallest psd cone that admits an affine slice that projects linearly onto the
polytope. The psd rank of a dpolytope is at least d+1, and when equality holds
we say that the polytope is psdminimal. In this paper we develop new tools for
the study of psdminimality and use them to give a complete classification of
psdminimal 4polytopes. The main tools introduced are trinomial obstructions,
a new algebraic obstruction for psdminimality, and the slack ideal of a
polytope, which encodes the space of realizations of a polytope up to
projective equivalence.
Our central result is that there are 31 combinatorial classes of psdminimal
4polytopes. We provide combinatorial information and an explicit psdminimal
realization in each class. For 11 of these classes, every polytope in them is
psdminimal, and these are precisely the combinatorial classes of the known
projectively unique 4polytopes. We give a complete characterization of
psdminimality in the remaining classes, encountering in the process
counterexamples to some open conjectures.

We show that the Euclidean distance degree of a real orthogonally invariant
matrix variety equals the Euclidean distance degree of its restriction to
diagonal matrices. We illustrate how this result can greatly simplify
calculations in concrete circumstances.

This paper considers the foundational question of the existence of a
fundamental (resp. essential) matrix given $m$ point correspondences in two
views. We present a complete answer for the existence of fundamental matrices
for any value of $m$. Using examples we disprove the widely held beliefs that
fundamental matrices always exist whenever $m \leq 7$. At the same time, we
prove that they exist unconditionally when $m \leq 5$. Under a mild genericity
condition, we show that an essential matrix always exists when $m \leq 4$. We
also characterize the six and seven point configurations in two views for which
all matrices satisfying the epipolar constraint have rank at most one.

Minimizing the Euclidean distance to a set arises frequently in applications.
When the set is algebraic, a measure of complexity of this optimization problem
is its number of critical points. In this paper we provide a general framework
to compute and count the real smooth critical points of a data matrix on an
orthogonally invariant set of matrices. The technique relies on "transfer
principles" that allow calculations to be done in the space of singular values
of the matrices in the orthogonally invariant set. The calculations often
simplify greatly and yield transparent formulas. We illustrate the method on
several examples, and compare our results to the recently introduced notion of
Euclidean distance degree of an algebraic variety.

The nearest point map of a real algebraic variety with respect to Euclidean
distance is an algebraic function. For instance, for varieties of low rank
matrices, the EckartYoung Theorem states that this map is given by the
singular value decomposition. This article develops a theory of such nearest
point maps from the perspective of computational algebraic geometry. The
Euclidean distance degree of a variety is the number of critical points of the
squared distance to a generic point outside the variety. Focusing on varieties
seen in applications, we present numerous tools for exact computations.

In this paper we show how to construct inner and outer convex approximations
of a polytope from an approximate cone factorization of its slack matrix. This
provides a robust generalization of the famous result of Yannakakis that
polyhedral lifts of a polytope are controlled by (exact) nonnegative
factorizations of its slack matrix. Our approximations behave well under
polarity and have efficient representations using second order cones. We
establish a direct relationship between the quality of the factorization and
the quality of the approximations, and our results extend to generalized slack
matrices that arise from a polytope contained in a polyhedron.

Given a set of point correspondences in two images, the existence of a
fundamental matrix is a necessary condition for the points to be the images of
a 3dimensional scene imaged with two pinhole cameras. If the camera
calibration is known then one requires the existence of an essential matrix.
We present an efficient algorithm, using exact linear algebra, for testing
the existence of a fundamental matrix. The input is any number of point
correspondences. For essential matrices, we characterize the solvability of the
Demazure polynomials. In both scenarios, we determine which linear subspaces
intersect a fixed set defined by nonlinear polynomials. The conditions we
derive are polynomials stated purely in terms of image coordinates. They
represent a new class of twoview invariants, free of fundamental
(resp.~essential)~matrices.

Let M be a pbyq matrix with nonnegative entries. The positive semidefinite
rank (psd rank) of M is the smallest integer k for which there exist positive
semidefinite matrices $A_i, B_j$ of size $k \times k$ such that $M_{ij} =
\text{trace}(A_i B_j)$. The psd rank has many appealing geometric
interpretations, including semidefinite representations of polyhedra and
informationtheoretic applications. In this paper we develop and survey the
main mathematical properties of psd rank, including its geometry, relationships
with other rank notions, and computational and algorithmic aspects.

This paper presents various worstcase results on the positive semidefinite
(psd) rank of a nonnegative matrix, primarily in the context of polytopes. We
prove that the psd rank of a generic ndimensional polytope with v vertices is
at least (nv)^(1/4) improving on previous lower bounds. For polygons with v
vertices, we show that psd rank cannot exceed 4ceil(v/6) which in turn shows
that the psd rank of a p by q matrix of rank three is at most
4ceil(min{p,q}/6). In general, a nonnegative matrix of rank (k+1 choose 2) has
psd rank at least k and we pose the problem of deciding whether the psd rank is
exactly k. Using geometry and bounds on quantifier elimination, we show that
this decision can be made in polynomial time when k is fixed.

The positive semidefinite (psd) rank of a polytope is the smallest $k$ for
which the cone of $k \times k$ real symmetric psd matrices admits an affine
slice that projects onto the polytope. In this paper we show that the psd rank
of a polytope is at least the dimension of the polytope plus one, and we
characterize those polytopes whose psd rank equals this lower bound. We give
several classes of polytopes that achieve the minimum possible psd rank
including a complete characterization in dimensions two and three.

In this paper we characterize the slack matrices of cones and polytopes among
all nonnegative matrices. This leads to an algorithm for deciding whether a
given matrix is a slack matrix. The underlying decision problem is equivalent
to the polyhedral verification problem whose complexity is unknown.

This article describes a method to compute successive convex approximations
of the convex hull of a set of points in R^n that are the solutions to a system
of polynomial equations over the reals. The method relies on sums of squares of
polynomials and the dual theory of moment matrices. The main feature of the
technique is that all computations are done modulo the ideal generated by the
polynomials defining the set to the convexified. This work was motivated by
questions raised by Lov\'asz concerning extensions of the theta body of a graph
to arbitrary real algebraic varieties, and hence the relaxations described here
are called theta bodies. The convexification process can be seen as an
incarnation of Lasserre's hierarchy of convex relaxations of a semialgebraic
set in R^n. When the defining ideal is real radical the results become
especially nice. We provide several examples of the method and discuss
convergence issues. Finite convergence, especially after the first step of the
method, can be described explicitly for finite point sets.

We propose a variant of the ChvatalGomory procedure that will produce a
sufficient set of facet normals for the integer hulls of all polyhedra {xx : Ax
<= b} as b varies. The number of steps needed is called the small Chvatal rank
(SCR) of A. We characterize matrices for which SCR is zero via the notion of
supernormality which generalizes unimodularity. SCR is studied in the context
of the stable set problem in a graph, and we show that many of the wellknown
facet normals of the stable set polytope appear in at most two rounds of our
procedure. Our results reveal a uniform hypercyclic structure behind the
normals of many complicated facet inequalities in the literature for the stable
set polytope. Lower bounds for SCR are derived both in general and for
polytopes in the unit cube.

Inspired by a question of Lov\'asz, we introduce a hierarchy of nested
semidefinite relaxations of the convex hull of real solutions to an arbitrary
polynomial ideal, called theta bodies of the ideal. For the stable set problem
in a graph, the first theta body in this hierarchy is exactly Lov\'asz's theta
body of the graph. We prove that theta bodies are, up to closure, a version of
Lasserre's relaxations for real solutions to ideals, and that they can be
computed explicitly using combinatorial moment matrices. Theta bodies provide a
new canonical set of semidefinite relaxations for the max cut problem. For
vanishing ideals of finite point sets, we give several equivalent
characterizations of when the first theta body equals the convex hull of the
points. We also determine the structure of the first theta body for all ideals.

In this paper we introduce several computational techniques for the study of
moduli spaces of McKay quiver representations, making use of Groebner bases and
toric geometry. For a finite abelian group G in GL(n,k), let Y_\theta be the
coherent component of the moduli space of \thetastable representations of the
McKay quiver. Our two main results are as follows: we provide a simple
description of the quiver representations corresponding to the torus orbits of
Y_\theta, and, in the case where Y_\theta equals Nakamura's GHilbert scheme,
we present explicit equations for a cover by local coordinate charts. The
latter theorem corrects the first result from [Nakamura]. The techniques
introduced here allow experimentation in this subject and give concrete
algorithmic tools to tackle further open questions. To illustrate this point,
we present an example of a nonnormal GHilbert scheme, thereby answering a
question raised by Nakamura.

For a finite abelian group G in GL(n,k), we describe the coherent component
Y_theta of the moduli space M_theta of thetastable McKay quiver
representations. This is a notnecessarilynormal toric variety that admits a
projective birational morphism to A^n/G obtained by variation of GIT quotient.
As a special case, this gives a new construction of Nakamura's GHilbert scheme
that avoids the (typically highly singular) Hilbert scheme of Gpoints in
A^n. To conclude, we describe the toric fan of Y_theta and hence calculate the
quiver representation corresponding to any point of Y_theta.

This is a survey article on Gorenstein initial complexes of extensively
studied ideals in commutative algebra and algebraic geometry. These include
defining ideals of Segre and Veronese varieties, toric deformations of flag
varieties known as Hibi ideals, determinantal ideals of generic matrices of
indeterminates, and ideals generated by Pfaffians of generic skew symmetric
matrices. We give a summary of recent work on the construction of squarefree
Gorenstein initial ideals of these ideals when the ideals are themselves
Gorenstein. We also present our own independent results for the Segre,
Veronese, and some determinantal cases.

This paper presents algorithms for computing the Groebner fan of an arbitrary
polynomial ideal. The computation involves enumeration of all reduced Groebner
bases of the ideal. Our algorithms are based on a uniform definition of the
Groebner fan that applies to both homogeneous and nonhomogeneous ideals and a
proof that this object is a polyhedral complex. We show that the cells of a
Groebner fan can easily be oriented acyclically and with a unique sink,
allowing their enumeration by the memoryless reverse search procedure. The
significance of this follows from the fact that Groebner fans are not always
normal fans of polyhedra in which case reverse search applies automatically.
Computational results using our implementation of these algorithms in the
software package Gfan are included.

The circuit ideal, $\ica$, of a configuration $\A = \{\a_1, ..., \a_n\}
\subset \Z^d$ is the ideal generated by the binomials ${\x}^{\cc^+} 
{\x}^{\cc^} \in \k[x_1, ..., x_n]$ as $\cc = \cc^+  \cc^ \in \Z^n$ varies
over the circuits of $\A$. This ideal is contained in the toric ideal, $\ia$,
of $\A$ which has numerous applications and is nontrivial to compute. Since
circuits can be computed using linear algebra and the two ideals often
coincide, it is worthwhile to understand when equality occurs. In this paper we
study $\ica$ in relation to $\ia$ from various algebraic and combinatorial
perspectives. We prove that the obstruction to equality of the ideals is the
existence of certain polytopes. This result is based on a complete
characterization of the standard pairs/associated primes of a monomial initial
ideal of $\ica$ and their differences from those for the corresponding toric
initial ideal. Eisenbud and Sturmfels proved that $\ia$ is the unique minimal
prime of $\ica$ and that the embedded primes of $\ica$ are indexed by certain
faces of the cone spanned by $\A$. We provide a necessary condition for a
particular face to index an embedded prime and a partial converse. Finally, we
compare various polyhedral fans associated to $\ia$ and $\ica$. The Gr\"obner
fan of $\ica$ is shown to refine that of $\ia$ when the codimension of the
ideals is at most two.

A short new proof of the fact that all shifted complexes are fixed by reverse
lexicographic shifting is given. A notion of lexicographic shifting,
$\Delta_{\lex}$  an operation that transforms a monomial ideal of
$S=\field[x_i: i\in\N]$ that is finitely generated in each degree into a
squarefree strongly stable ideal  is defined and studied. It is proved that
(in contrast to the reverse lexicographic case) a squarefree strongly stable
ideal $I\subset S$ is fixed by lexicographic shifting if and only if $I$ is a
universal squarefree lexsegment ideal (abbreviated USLI) of $S$. Moreover, in
the case when $I$ is finitely generated and is not a USLI, it is verified that
all the ideals in the sequence $\{\Delta_{\lex}^i(I)\}_{i=0}^{\infty}$ are
distinct. The limit ideal $\bar{\Delta}(I)=\lim_{i\to\infty}\Delta_{\lex}^i(I)$
is well defined and is a USLI that depends only on a certain analog of the
Hilbert function of $I$.