ARAG Conference Schedule

On Thursday and Friday, talks will be held in the Main building of Aalto university in Otaniemi (klick here for a map of the campus) (Otakaari 1, 02150 Espoo) in lecture hall E. On Saturday and Sunday in lecture hall M1 (klick here for a map of the building)
Thursday February 27 Friday February 28 Saturday March 1 Sunday March 2
9:00 - 9:20
Welcome
9:00 - 9:30
Coffee (Room 2nd floor)
9:00 - 9:30
Coffee
9:00 - 9:30
Coffee
9:30 - 10:30 : Room E
Schweighofer
9:30 - 10:30 : Room E
Putinar
9:30 - 10:30 : Room M1
Ranestad
9:30 - 10:30 : Room M1
Contributed talks (Trabandt/Theran)
11:00-12:00 Room E
Scheiderer
11:00 - 12:00 Room E
Lasserre
11:00 - 12:00 Room M1
Uhler
11:00 - 12:30 Room M1
Contributed talks
(Violet/Kummer/Martin del Campo)
     
13:30 - 14:30 : Room E
Roy
13:30 - 14:30 Room E
Basu
13:30 - 14:30 Room M1
Vallentin
14:30 - 15:30 :
Coffee
14:30 - 15:30 :
Coffee
14:30 - 15:30 :
Coffee
15:30 - 17:30
Campus Tour
15:30 - 16:30 Room E
Contributed talks
(Sjöland/De Laat)
15:30 - 16:30 Room M1
Contributed talks (Robeva/Hanselka)
18:00
Details on dinner options
17:00 - 18:00 Room E
Contributed talks (Norén/Karasoulou)
17:00 - 18:00 Room M1
Contributed talks
(Magron/Grande)


Invited Speakers

Markus SchweighoferThursday , 9:30 - 10:30
On sums of squares decompositions of univariate matrix polynomials
Markus Schweighofer
We review a method suggested by Parrilo et al. to compute a sums of squares representation of a symmetric matrix polynomial positive definite on the real line. We show that it sometimes fails and that a modified version often works. (joint work with Christoph Hanselka and Bernd Mangold)

Claus ScheidererThursday, 11:00 - 12:00
Sums of squares of polynomials with rational coefficients
Claus Scheiderer
We consider multivariate polynomials f with rational coefficients which are sums of squares of polynomials with real coefficients. Such f has a sum of squares representation with coefficients in some finite real extension K of Q, but not necessarily in Q itself. We shall attempt to provide more information on possible fields K, and to give sufficient conditions that imply the existence of a representation over Q.

Marie Francoise RoyThursday, 13:30 - 14:30
Elementary recursive bounds for Hilbert 17 th problem
Marie-Francoise Roy
Hilbert 17th problem is to express a non-negative polynomial as a sum of squares of rational functions. The original proof by Artin is non-constructive and gives no information on the degree bounds. A more general problem is to give an identity which certifies the unrealizability of a system of polynomial equations and inequalities. The existence of such an identity is guaranteed by the Positivstellensatz. We give a new constructive proof which provides elementary recursive bounds for the Positivstellensatz and Hilbert 17 problem, namely a tower of five levels of exponentials. (joint work with Daniel Perrucci and Henri Lombardi)

Mihai PutinarFriday, 9:30 - 10:30
Polynomial inequalities derived from numerical range of matrices
Mihai Putinar
Based on the identification of operators with a cyclic vector and duals of certain convex cones of polynomials, one relates recent advances on uniform estimates of the harmonic functional calculus on the numerical range of a matrix to a series of new polynomial inequalities.

Jean Bernard LsserreFriday, 11:00 - 12:00
Reconstruction of algebraic-exponential data from moments.
Jean Bernard Lasserre
Let G be a bounded open subset of Euclidean space with real algebraic boundary Γ. We first consider the case where G={x: g(x) <=1} for some quasi-homogeneous polynomial "g" and derive several properties of "G" as well as the non-Gaussian integral ∫ exp(-g)dx. Next, we consider a more gneral case and under the assumption that the degree d of Γ is given, and the power moments of the Lebesgue measure on G are known up to order 3d, we describe an algorithmic procedure for obtaining a polynomial vanishing on Γ. The particular case of semi-algebraic sets defined by a single polynomial inequality raises an intriguing question related to the finite determinateness of the full moment sequence. The more general case of a measure with density equal to the exponential of a polynomial is treated in parallel. Our approach relies on Stokes theorem and simple Hankel-type matrix identities. (joint work with M. Putinar)

Saugata BasuFriday, 13:30 - 14:30
Towards a real analogue of the Bezout inequality and applications to incidence problems.
Saugata Basu

The classical theorem of Bezout implies that the number of isolated complex zeros of k polynomials in [X1,,Xk] is bounded by the product of the degrees of the polynomials. It is also well known that the same statement does not hold over the real numbers, or more generally over real closed fields. In this talk I will explain a new result that could serve as a substitute. Let R be a real closed field and Q1,,Q R[X1,,Xk]such that for each i, 1 i , deg(Qi) di. For 1 i ,denote by Qi = {Q1,,Qi}, V i the real variety defined by Qi, and ki an upper bound on the real dimension of V i (by convention V 0 = Rk and k 0 = k). Suppose also that

2 ≤ d  ≤ d  ≤ --1---d  ≤ ----1---d  ≤ ⋅⋅⋅ $
     1    2   k + 1  3   (k + 1)2 4         (k + 1)ℓ-3 ℓ-1   (k + 1)ℓ-2 ℓ

and that k. We prove that the number of semi-algebraically connected components of V is bounded by       (             )
     2k   ∏     kj-1-kj   kℓ-1
O (k )         dj       dℓ   .
         1≤j< ℓ

I will also explain why this result could be of interest in tackling incidence problems in discrete geometry. (Joint work with Sal Barone.)

Kristian RanestadSaturday, 9:30 - 10:30
Quartic spectrahedra
Kristian Ranestad
Quartic spectrahedra in 3-space are convex semialgebraic sets of semidefinite real 4x4 matrices. Their algebraic boundary are quartic surfaces with in general 10 complex nodes, studied classically by Cayley. Degtyarev and Itenberg have identified the possible number of real nodes on the spectrahedron using Torelli's theorem for K3 surfaces. I will present an elementary proof of their result based on a real version of Cayleys results, reporting on recent work with Ottem, Sturmfels and Vinzant.

Caroline UhlerSaturday 11:00 - 12:00
Real algebraic geometry and causal inference
Caroline Uhler
Many algorithms for inferring causality are based on partial correlation testing. Partial correlations define hypersurfaces in the parameter space of a directed Gaussian graphical model. The volumes obtained by bounding partial correlations play an important role for the performance of causal inference algorithms and the quantification of bias in causal inference. We develop an asymptotic theory for computing these volumes. Our analysis involves computing the real singular loci of the partial correlation hypersurfaces and using the method of real log canonical thresholds.

Frank VallentinSaturday, 13:30 - 14:30 pm
Semidefinite programming bounds for codes and anticodes in Cayley graphs
Frank Vallentin
Many, often notoriously difficult, packing problems in combinatorics and geometry can be formulated as coding or anticoding problems in Cayley graphs. Examples include k-intersecting families of permutations, sets in n-dimensional Euclidean space avoiding the unit distance, or packings of congruent copies of a convex and compact body in Euclidean space. The best known upper bounds for the optimal packing density come in many cases from a uniform spectral technique. In the talk I will discuss this approach which uses semidefinite programming and harmonic analysis. I show how to compute the bounds and present some results.

 

Contributed talks

Feb 28 15:30
Eric Sjöland (Aalto)
Counting arithmetic progressions using semidefinite programming
One of the most challenging problems in Ramsey theory is to count the minimal number of monochromatic arithmetic progressions in a group colored in c colors. Based on Putinar's positivstellensatz it is possible to rewrite the problem as a semidefinite program. Inspired by methods developed by de Klerk, Pasechnik and Schrijver we reduce the size of the problem by understanding its symmetries. The approach is applicable for any group, including non-abelian groups. We present novel results for several infinite families of groups.
Feb 28 16:00
David de Laat (TU Delft)
A semidefinite programming hierarchy for packing problems in discrete geometry
Packing problems in discrete geometry can be modeled as maximum independent set problems in infinite graphs. Computing the independence number (the size of a maximum independent set) of a finite graph is NP-hard, but the Lasserre hierarchy from polynomial optimization can be used to compute good upper bounds. We generalize this hierarchy to infinite graphs. This yields a hierarchy of infinite dimensional optimization problems and by using harmonic analysis and SOS characterizations these can be approximated by finite dimensional semidefinite programs. For finite graphs it is known that the hierarchy converges to the independence number; we show that this also holds for the class of infinite graphs corresponding to geometric packing problems.
Feb 28 17:00
Patrik Norén (IST)
Volumes of convex hulls of curves
The convex hull of a curve or a piece of a curve is a semi algebraic set. Computing the volume of these sets is in general a challenging problem. For the convex hull of a piece of a generalised moment curve we provide a formula for the volume. This formula involves a generalisation of the Selberg integral and solves a problem by Ottaviani concerning matrix rank.
Feb 28 17:30
Anna Karasoulou (University of Athens)
A factorization formula for the discriminant of a symmetric homogeneous polynomial and of the resultant of globally invariant systems under S_{n}.
Polynomial equations and their respective systems are crucial in various scientific and technological applications. Their solution is one of the fundamental problems of Computational Algebraic Geometry. The discriminant is a very useful tool, when examining such systems, but also hard to compute. We present a factorization formula for the discriminant of symmetric polynomials. The same technique can be also applied to resultants of globally invariant systems under the the action of the symmetric group.
March 1 15:30
Elina Robeva (Berkeley)
Fixed points of the EM algorithm and nonnegative rank boundaries
Matrices of nonnegative rank $r$ represent mixtures of $r$ independent distributions. Likelihood inference for this model leads to problems in real algebraic geometry that will be addressed in this talk. We characterize the fixed point locus of the Expectation Maximization algorithm, and we study the boundary of the space of matrices with nonnegative rank at most $3$. Both of these are algebraic varieties with many irreducible components.
March 1 16:00
Christoph Hanselka (University of Konstanz)
Symmetric Determinantal Representations of Ternary Hyperbolic Polynomials
Hyperbolicity cones are certain convex cones defined by hyberbolic polynomials, i.e. forms, that have only real roots on every line in a given direction. The Theorem of Helton and Vinnikov states that every such polynomial in three variables has a definite real symmetric determinantal representation, in particular implying that every hyperbolicity cone can be described by a linear matrix inequality. The talk will be concerned with a more algebraic and elementary proof of this theorem.
March 1 17:00
Victor Magron (Toulouse)
Approximating Pareto curves using Semidefinite Relaxations
We consider the problem of constructing an approximation of the Pareto curve associated with the multiobjective polynomial optimization problem min{f(x) : x \in S}, where f(x) := (f1(x), f2(x)) is a vector of two conflicting polynomial criteria and S is a compact semialgebraic set. We present two methods to tackle this problem. First, we show that the computation of the Pareto curve can be treated as an inverse problem from generalized moments. Alternatively, one can build certified polynomial underestimators of the curve by computing a hierarchy of outer approximations of f(S). In both cases, the proposed numerical schemes avoid computing finitely many points. (joint work with Jean-Bernard Lasserre and Didier Henrion)
March 1 17:30
Francesco Grande (FU Berlin)
Theta rank, levelness, and matroids
Gouveia, Parrilo, and Thomas (2010) introduced the Theta rank of a finite point configuration as the smallest k for which the k-th Lasserre relaxation is exact. They characterized configurations of minimal Theta rank via the levelness of the configuration. Classification results for general Theta rank (or levelness) seem out of reach. In this talk I will investigate point configurations arising from matroids. In this setting Theta rank and levelness can be phrased combinatorially which yields classification results in terms of excluded minors. This is joint work with Raman Sanyal.
March 2 9:30
Christian Trabandt (Frankfurt)
A new error bound for Handelman's and Schmüdgen's Positivstellensatz
We provide a new error bound for polynomial optimization over a polytope $P$ with Handelman's and Schmüdgen's Positivstellensatz, making use of the similarity of the Handelman representation on boxes with Bernstein polynomials. Building upon work by de Klerk and Laurent, we provide a bound that depends on the length of the longest edge of a bounding box of the polytope $P$. Our results imply that the Positivstellensatz approach can be combined with a branch and bound procedure to gain accuracy without elevating the degree bound.
March 2 10:00
Louis Theran (FU Berlin)
Dual-to-kernels learning and dimension reduction
In this talk, I’ll show how just one SVD is enough to summarize a high-dimensional point set by its approximate vanishing ideal. This is efficient enough for “big data” scenarios, in contrast to, e.g., algorithms relying on term enumeration or Gröbner basis reductions. The main underlying idea is to formulate algebraic dimension reduction as a generative dual to the Vapnik-Chervonenkis of discriminative learning. This is joint work with Franz Király and Martin Kreuzer.
March 2 11:00
Grey Violet (Moscow)
Real algebraic geometry in robust control: root invariant regions of a parameter space
We will consider applications of real algebraic geometry to the study of stability for robust linear control systems. Аlgorithms for the study of a decomposition of parameter space into root invariant regions will be presented, as well as some estimates on the number of such a regions.
March 2 11:30
Mario Kummer (University of Konstanz)
Determinantal Representations of Hyperbolic Polynomials
A major open question in convex algebraic geometry is whether all hyperbolicity cones are spectrahedral, i.e. the solution sets of linear matrix inequalities. We will use sum-of-squares decompositions of certain matrix polynomials to approach this problem. More precisely, we will prove that for every smooth hyperbolic polynomial h there is another hyperbolic polynomial q such that qh has a definite determinantal representation.
March 2 12:00
Abraham Martin del Campo (IST)
Experimentation in the Schubert Calculus
Schubert calculus is an important class of geometric problems involving linear spaces meeting other fixed but general linear spaces. The Galois group of a problem in Schubert calculus is a subtle invariant that encodes intrinsic structure in its set of solutions. Many aspects of Schubert calculus are easily modeled on a computer. This enables large-scale experimentation to investigate subtle and ill-understood phenomena in the Schubert calculus. A well-known web of conjectures and results in the real Schubert calculus has been inspired by this continuing experimentation. A similarly rich story concerning Galois groups of Schubert problems is also beginning to emerge from experimentation. Preliminary results suggest phenomena to study in future large-scale computational experiments. For example, most Schubert problems have highly transitive Galois groups that contain the alternating group, while the rest are only singly transitive, and the intrinsic structure restricting their Galois groups also restricts their possible numbers of real solutions.
Each of the contributed talks is scheduled to be 25-30 minutes.

 

Conference Dinner

We will have a dinner on Friday evening at Tony's Delis in dowton Helsinki (Bulevardi 7). If you are interested to join in, please sign up as soon as possible.

 

Campus tour

Aalto University was established in 2010 in the merger of the Helsinki University of Technology, the Helsinki School of Economics, and the University of Art and Design Helsinki. The conference will be hosted on technology campus which is located in Otaniemi. This campus was built in the 1960s, when the then Helsinki University of Technology moved from downtown Helsinki to its current Otaniemi. It was designed by Alvar Aalto and features buildings from Aalto's "redbrick period". Besides these architectural amongst which the Auditorium is the most prominent one, the campus hosts several high-tech companies and business incubators. We pan to have a short tour on the campus to present this new concept to the participants.

 

Dinner options in Helsinki

Downtown Helsinki offers a wide range of excellent options for dinner. Especially on the first evening we will provide detailed information on the various dinner options in Helsinki.

Program note: This page features a preliminary program. Check back frequently to find the most up-to-date information.