Saugata Basu Toda's theorem -- real and complex. We study the relationship between the computational hardness of two well-studied problems in algorithmic semi-algebraic as well as complex geometry -- namely the problem of deciding sentences in the first order theory of reals/complex numbers with a constant number of quantifier alternations, and that of computing Betti numbers of semi-algebraic/constructible sets. We obtain a polynomial time reduction of the compact version of the first problem to the second. As a consequence we obtain analogues of Toda's theorem from discrete complexity theory over the reals as well as complex numbers. (Part of this work is joint with Thierry Zell). --------------------------------------------------------- Greg Blekherman Convex Forms and Faces of the Cone of Sums of Squares We will describe a simple proof based on volumes that there exist convex forms that are not sums of squares. A convex form has to be nonnegative and there are currently no explicit examples of such forms. A prerequisite for constructing such an example would be building strictly positive forms that are not sums of squares. We will describe the facial structure of the cone of nonnegative forms and build explicit faces of the cone of sums of squares that contain strictly positive forms, which leads to strictly positive polynomials that are not sums of squares. ------------------------------------------------------ Petter Braenden Title: Tropicalization of hyperbolic polynomials Abstract: We study the tropicalization of a class of hyperbolic polynomials, namely the stable polynomials. We prove that the tropicalization of stable polynomials is a proper subspace of the space of $M$-concave functions studied by Murota. We also describe the relationship with the tropical Grassmannian and the Dressian. Finally we provide a short proof of Speyer's hive theorem. -------------------------------------------------------- Harm Derksen (Poly)Matroid Polytopes To a matroid, or more generally, a polymatroid one can associate its base polytope. Many interesting invariants, such as the Tutte polynomial, the Billera-Jia-Reiner quasi-symmetric function F, and the quasi-symmetric function G introduced by the speaker, are valuative. Valuative functions are functions which can be described as integrating a function over the polymatroid polytope with respect to some measure. In this talk, we will explicitly describe explicitly all valuative functions and all valuative invariants. In particular, this shows that G is universal with respect to all valuative invariants. This is joint work with Alex Fink. ------------------------------------------------------- Jonathan Hauenstein Numerical algebraic geometry The field of numerical algebraic geometry consists of numerical-based algorithms for solving polynomial systems and manipulation positive-dimensional solution components. Such algorithms have many applications in convex algebraic geometry and optimization as well as science and engineering in general. The first part of this talk will review two fundamental ideas of numerical algebraic geometry, namely homotopy continuation and the numerical irreducible decomposition. This talk will conclude by describing regeneration and computing rank-deficiency sets of a matrix with multivariate polynomial entries. --------------------------------------------- Martin Henk Representing Polyhedra by Few Polynomials By a theorem of Br"ocker and Scheiderer, every basic closed semi-algebraic set in R^n can be described by at most n(n+1)/2 polynomial inequalities. All known proofs of this result are highly non-constructive. Here we are interested in algorithmic constructions of such a representation by few polynomials for the very special class of semi-algebraic sets consisting of polyhedra. The talk reviews recent results on this problem. -------------------------------------------------------- Erich Kaltofen Certifying the Radius of Positive Semidefiniteness Via Our ArtinProver Package We give a stability criterion for real polynomial inequalities with floating point or inexact scalars by estimating from below or computing the radius of positive semidefiniteness. The stability radius is the maximum deformation of the polynomial coefficient vector measured in a weighted Euclidean vector norm within which the inequality remains true. A large radius means that the inequalities are numerically stable. The stability radius is the distance to the nearest polynomial with a real root. We solve this problem by parameterized Lagrangian multipliers and Karush-Kuhn-Tucker conditions. Our algorithms can compute the stability radius for several simultaneous inequalities and with additional linear coefficient constraints. The computation of the nearest polynomial with a real root can be interpreted as a dual of Seidenberg's method that decides if a real hypersurface contains a real point. Sums of squares rational lower bound certificates for the radius of positive semidefiniteness provide a new approach to solving Seidenberg's problem, especially when the coefficients are numeric. Joint work with Sharon Hutton and Lihong Zhi. ------------------------------------------------------------- Oliver Labs Towards Visualization Tools for Convex Algebraic Geometry We present some preliminary tools to visualize convex algebraic geometry. Some are based on our software SURFEX which is a software for visualizing real algebraic varieties in three-space. Some others are based on MATLAB and its SDP computation features. Together with Ph. Rostalski, we plan to provide a set of tools using these two approaches. Feel free to contact us for preliminary versions. --------------------------------------------------------- Monique Laurent (CWI, Amsterdam, and Tilburg University) Error and degree bounds for positivity certificates on the hypercube We consider the problem of testing whether a polynomial is positive on a compact basic closed semi-algebraic set $K$, and of approximating its minimum over $K$. As is well known, positivity certificates have been given by Schm\"udgen [1991] and by Putinar [1993], involving respectively the preordering and the quadratic module generated by the polynomials inequalities defining $K$. Degree bounds and error estimates have been proved for these two types of representations by Schweighofer [2004] and by Nie and Schweighofer [2007]. These results involve some unknown constants depending only on the set $K$. In this talk we give explicit degree and error bounds for representations in the preordering in the case when $K$ is the hypercube $[0,1]^n$, which imply in particular that the unknown constants can be chosen equal to 1. Our results are elementary and rely on using Bernstein approximations. This is joint work with Etienne de Klerk (Tilburg University). ----------------------------------------------------- Murray Marshall Lower bounds for a polynomial in terms of its coefficients We determine new sufficient conditions in terms of the coefficients for a polynomial $f$ of degree $2d$ in $n$ variables to be a sum of squares of polynomials, thereby strengthening results of Fidalgo and Kovacec and of Lasserre. Exploiting these results, we determine, for any polynomial $f$ of degree $2d$ whose highest degree term is an interior point in the cone of sums of squares of forms of degree $d$, a real number $r$ such that $f-r$ is a sum of squares of polynomials. The existence of such a number $r$ was proved earlier, but no estimates for $r$ were given. We also determine a lower bound for any polynomial $f$ whose highest degree term is positive definite. This is joint work with Mehdi Ghasemi. ------------------------------------------------------ Tim Netzer Spectrahedra and their projections Spectrahedra are sets defined by linear matrix inequalities. Both spectrahedra and their projections are feasible sets for semidefinite programming. The question which sets are spectrahedra or arise as their projections has recently gained a lot of interest. I will explain some of the most important results and present some new. ------------------------------------------------------ Daniel Plaumann Exposed faces and projections of spectrahedra A spectrahedron is a convex set defined by a linear matrix inequality. It is known that every face of a spectrahedron is exposed. This is true more generally of rigidly convex sets. We study the same question for projections of spectrahedra. Our main result is that Lasserre's moment matrix method can only work for a convex set if all its faces are exposed. This necessary condition complements sufficient conditions recently proved by Lasserre, Helton and Nie. (joint work with Tim Netzer and Markus Schweighofer) ---------------------------------------------------- Mihai Putinar Optimization of non-polynomial functions and applications When trying to apply to Borel measurable functions the optimization scheme advocated by Jean-Bernard Lasserre in the last decade in the case of polynomials, one encounters a series of natural, but far from trivial questions. The first is to characterize the moments of positive Borel measures with respect to various bases of functions, such as exponentials, Haar systems, wavelets, trigonometric functions or fractional powers of the coordinates. Second, it is necessary to saturate Archimedean quadratic modules of such functions, so that the solvability of the moment problem with prescribed supports can be achieved effectively, buy a sequence of positivity assumptions. Last, after passing to the moment coordinate framework, a filtration given by the degree should converge (fast enough) to the solution of the original optimization problem. Applications to systems of difference and differential equations with delays in the argument will be discussed. Based on joint work in progress with Jean- Bernard Lasserre and Silviu Niculescu. -------------------------------------------------------------------- Kristian Ranestad The convex hull of a space curve The boundary of the convex hull of a compact algebraic curve in real 3-space defines a real algebraic surface. For general curves, that boundary surface is reducible, consisting of tritangent planes and a scroll of stationary bisecants. In recent work with Sturmfels we extend classical formulas to express the degree of this surface in terms of the degree, genus and singularities of the curve. For rational curves we present methods for computing their defining polynomials, and exhibit a range of examples. --------------------------------------------- Jim Renegar Optimization Over Hyperbolicity Cones After a brief survey of basic results on multivariate hyperbolic polynomials, and on the derivative relaxations of hyperbolic programs (= linear optimization over hyperbolicity cones), we introduce the notion of central swaths, which although not immediately obvious, happen to be (substantial) generalizations of the central path ubiquitous in the interior-point method literature. We display a simple and natural dynamics for generating paths in the swaths, paths guaranteed to lead to optimality. Finally, we present some key ingredients for a mathematical analysis of algorithms in following these paths (but a complete analysis has yet to be accomplished). --------------------------------------------- Bruce Reznick The cones of real convex forms For each (n,m), let K_{n,m} denote the set of real forms p(x_1,...,x_n) of degree m which are convex as functions. Then K_{n,m} is a closed convex cone. The extremal elements for m=2 and n=2 will be discussed, and completely described for K_{2,4} and K_{2,6}. One extremal form is x^6 + 5(3/2)^(2/3) x^2 y^4 + y^6. Each K_{n,m} is an example of a blender, as defined by the speaker 20 years ago. Under the natural inner product, the dual cone is generated by all products L_1^2*L_2^{m-2}, where the L_i's are real linear forms. Let f(x_1,...,x_{n-1}) = p(x_1,...,x_n) be a dehomogenization of p. It is apparently well-known to some analysts that p is convex iff f^{1/m} is convex as a function in n-1 variables. Blekherman has proved that for fixed m, the probability that a convex form is a sum of squares of forms goes to zero as n goes to infinity, but he's been unable to find a single example of a convex form which is not a sum of squares. Alas, neither has the speaker. --------------------------------------------------------- Philipp Rostalski SDP Relaxations for the Grassmann Orbitope The Grassmann orbitope is the convex hull over the Grassmann variety of decomposable skew-symmetric tensors of unit length. This variety parametrizes k-dimensional linear subspaces of R^n, and it is the highest weight orbit under the k-th exterior power representation of the group SO(n). In this talk we discuss semidefinite relaxations of the Grassmann orbitope. That convex body can be approximated and represented surprisingly well by projections of spectrahedra (using Lasserre's moment matrices). We show that the first relaxation is exact for k=2, we present numerical evidence that this result extends to higher k, and we discuss relations to a longstanding conjecture on calibrations by Harvey and Lawson. If time permits, we discuss three additional classes of orbitopes and explain why the relaxation order is related to a certain polytope. This is a joint project with Raman Sanyal and Bernd Sturmfels. ------------------------------------------------------ Claus Scheiderer Bounded polynomials and stability of preorderings Given a semi-algebraic set S, we study the ring B(S) of polynomials bounded on S, and we discuss some results on the structure of B(S) from the last years (joint work with D. Plaumann). We review the concepts of stability and strict stability for preorderings and quadratic modules, and we point to some open questions relating those to bounded polynomials. We finally show that the use of toric completions can greatly simplify the study of bounded polynomials and of stability for certain classes of semi-algebraic sets. ------------------------------------------------- Gregory G Smith Determinantal Equations We prove that every projective embedding of a connected scheme determined by the complete linear series of a sufficiently ample line bundle is defined by the (2×2)-minors of a 1-generic matrix of linear forms. Extending the work of Eisenbud-Koh-Stillman for integral curves, we also provide effective descriptions for such determinantally presented ample line bundles on products of projective spaces, Gorenstein toric varieties, and smooth n-folds. --------------------------------------------------------- Frank Sottile Orbitopes An orbitope is the convex hull of an orbit of a compact group acting linearly on a vector space. Instances of these highly symmetric conex bodies have appeared in many areas of mathematics and its applications, including protein reconstruction, symplectic geometry, and calibrations in differential geometry. In this talk, I will discuss Orbitopes from the perpectives of classical convexity, algebraic geometry, and optimization with an emphasis on ten motivating problems and concrete examples. This is joint work with Raman Sanyal and Bernd Sturmfels. ---------------------------------------------------- Thorsten Theobald (Goethe-Universität Frankfurt): Amoebas of genus at most 1 The amoeba $\mathcal{A}(f)$ of a polynomial $f \in \mathbb{C}[x_1, \ldots, x_n]$ is the image of the variety $V(f) \subset (\mathbb{C}^*)^n$ under the map $\Log z := (\log |z_1|, \ldots, \log |z_n|)$. It is well-known that the complement of \mathcal{A}(f) consists of finitely many convex components. In general, understanding the configuration space of amoebas is widely open. In this talk, we study a subclass of amoebas where the Newton polytope of $f$ is a simplex with one inner support point. Thus there are only two possible homotopy types. We give bounds on the inner coefficients for either of the two genera and give characterizations for the two genera in terms of lopsidedness and in terms of the $A$-discriminant. (Joint work with Timo de Wolff.) -------------------------------------------------- Frank Vallentin Approximation algorithms for SDPs with rank constraints Abstract: Finding a sparse/low rank solution in linear/semidefinite programming has many important applications, e.g. combinatorial optimization, compressed sensing, geometric embedding, sensor network localization. In this talk we will consider one of the most basic problems involving semidefinite programs with rank constraints: the Grothendieck problem with rank-k-constraint. It contains the MAX CUT problem as a special case when k = 1 and it is closely related to Grothendieck inequalities which have been studied in optimization, functional analysis, combinatorics, quantum information theory, and complexity theory. We will perform a complete complexity analysis of the the positive semidefinite version problem by designing an approximation algorithm and by proving that the algorithm is optimal if one assumes the unique games conjecture. joint work with Jop Briët and Fernando de Oliveira Filho (http://arxiv.org/abs/0910.5765). ------------------------------------------------------------- Cynthia Vinzant (University of California, Berkeley) Faces of the Barvinok-Novik orbitope In 2008, Barvinok and Novik studied faces of the convex hull of the odd trigonometric moment curve. They show that this convex body is locally k-neighborly and use this to construct centrally symmetric polytopes with high face numbers. We will review these results and resolve one the conjectures from their paper, which leads to a complete characterization of the edges of this orbitope. In small dimensions we'll be able to see many other faces as well. -----------------------------------------------------