A polytrope is a convex polytope that is expressed as the tropical convex hull of a finite number of points. It is well known that every bounded cell of a tropical linear space is a polytrope, and its converse statement has been a conjecture. We develop an elementary approach to the relationship between tropical convexity and tropical linearity, and show that the conjecture holds in dimension up to 3 and fails in every higher dimension. Thus, tropical convexity is strictly bigger than tropical linearity.

We portray the evolution of the Covid-19 epidemic during the crisis of March-April 2020 in the Paris area, by analyzing the medical emergency calls received by the EMS of the four central departments of this area (Centre 15 of SAMU 75, 92, 93 and 94). Our study reveals strong dissimilarities between these departments. We show that the logarithm of each epidemic observable can be approximated by a piecewise linear function of time. This allows us to distinguish the different phases of the epidemic, and to identify the delay between sanitary measures and their influence on the load of EMS. This also leads to an algorithm, allowing one to detect epidemic resurgences. We rely on a transport PDE epidemiological model, and we use methods from Perron-Frobenius theory and tropical geometry.

Steiner posed the question if any 3-dimensional polytope had a realization with vertices on a sphere. Steinitz constructed the first counter examples and Rivin gave a complete resolution. In dimensions 4 and up, Mnev's universality theorem renders the question for inscribable combinatorial types hopeless. In this talk, I will address the following refined question: Given a polytope P, is there a normally equivalent polytope with vertices on a sphere? That is, can P be deformed into an inscribed polytope while preserving its normal fan? It turns out that the answer gives a rich interplay of geometry and combinatorics, involving local reflections and type cones. This is based on joint work with Sebastian Manecke (who will continue the story in the FU discrete geometry seminar next week).

In the geometry of polynomials, the notion of stability is of prominent importance. The purpose of the talk is to discuss its recent generalization to conic stability. Given a convex cone K in real n-space, a multivariate polynomial f in C[z] is called K-stable if it does not have a root whose vector of the imaginary parts is contained in the interior of $K$. If $K$ is the non-negative orthant, then $K$-stability specializes to the usual notion of stability of polynomials. In particular, we focus on $K$-stability with respect to the positive semidefinite cone and develop stability criteria building upon the connection to the containment problem for spectrahedra, to positive maps and to determinantal representations. These results are based on joint work with Papri Dey and Stephan Gardoll.

Classically, there is a rich theory in algebraic combinatorics surrounding the various objects associated with a generic real matrix. Examples include regular triangulations of the product of two simplices, coherent matching fields, and realizable oriented matroids. In this talk, we will extend the theory by skipping the matrix and starting with an arbitrary triangulation of the product of two simplices instead. In particular, we show that every polyhedral matching field induces oriented matroids. The oriented matroid is composed of compatible chirotopes on the cells in a matroid subdivision of the hypersimplex. Furthermore, we give a corresponding topological construction using Viro’s patchworking. This talk will also sketch the relationship between Baker-Bowler’s matroids over hyperfields and our work. This is joint work with Marcel Celaya and Chi-Ho Yuen.

In this talk I will describe very recent work on analyzing different models of auto-encoder neural networks using random polytopes. In general, a class of neural networks known as auto-encoders can be understood as a low- dimensional (piecewise linear) embedding ℝᴺ → ℝⁿ (with N >> n), where points in the domain are e.g. images (in their pixel form) and each dimension the range extracts a single "feature".
Although understanding the properties of these embedings is crucial for explainability (e.g. interpreting the decisions taken by the network), the research in this direction has been undertaken only from the statistical point of view. We introduce `random polytope descriptors` which try to approximate datasets in the feature space by possibly tight convex bodies. This is the first attempt at understanding the very coarse geometry of embeddings provided by neural networks. Using such descriptors one can answer e.g. if the natural clusters of of images has been preserved or distorted by the neural network, and if the embedding actually separates them (the question of entanglement).
We use random polytope descriptors to examine the behaviour of auto-encoder networks in both vanilla and variational form, and provide first evidence for susseptibility of the latter to out-of-distribution attacks.
This is joint work with L.Ruffs (TUB, Department of Electrical Engineering and Computer Science) and M.Joswig (TUB, Chair of Discrete Mathematics/Geometry; MPI for Mathematics in the Sciences, Leipzig).

Many fundamental topological problems about 3-manifolds are algorithmically solvable in theory, but continue to withstand practical computations. In recent years some of these problems have been shown to allow efficient solutions, as long as the input 3-manifold comes with a sufficiently "thin" presentation.
More specifically, a 3-manifold given as a triangulation is considered thin, if the treewidth of its dual graph is small. I will show how this combinatorial parameter, defined on a triangulation, can be linked back to purely topological properties of the underlying manifold. From this connection it can then be followed that, for some 3-manifolds, we cannot hope for a thin triangulation.
This is joint work with Krist�f Husz�r and Uli Wagner

A discriminant is a subset of a function space consisting of singular functions. We shall consider discriminants of finite dimensional vector spaces of polynomials defining hypersurfaces in a toric variety. In the best case scenario (for plane curves for example), the discriminant is an irreducible hypersurface, however this is not the case for almost any other toric variety. We discuss positive results on the geometry of discriminants of weighted projective spaces and how to compute them via the A-discriminants of Gelfand, Kapranov and Zelevinsky.

I will report on the implementation of hyperplane arrangements in polymake. Hyperplane arrangements appear in a wide variety of applications in tropical and algebraic geometry. An important construction is the induced subdivision. We will discuss the new HyperplaneArrangement object, its properties and our simple algorithm for constructing the cell subdivision.
This is joint work with Marta Panizzut.

We consider a model for generating non-simple, non-simplicial random polytopes. The first step of the random process generates a random polytope P via random hyperplanes tangent to the d-dimensional sphere; the second step is given by the convex hull of a binomial sample of the vertices of P. In this talk we will discuss some ongoing work establishing results about the expected complexity of such polytopes.

Tropically planar graphs are graphs that arise as the skeletons of smooth tropical plane curves, which are dual to regular unimodular triangulations of lattice polygons. In this talk we study what geometric properties such graphs have in the moduli space of metric graphs, as well as the combinatorial properties these graphs satisfy. This talk will include older work with Brodsky, Joswig, and Sturmfels; newer work with Coles, Dutta, Jiang, and Scharf; and ongoing work with Tewari.

In this talk I will present a model for the realization space of a polytope which represents a polytope by its slack matrix. This model provides a natural algebraic relaxation for the realization space, and comes with a defining ideal which can be used as a computational engine to answer questions about the realization space. We will see how this model is related to more classical realization space models (representing realizations by Gale diagrams or points of the Grassmannian). In particular, we will see these relationships can be used to improve computational efficiency of the slack model.

In 2010, Stapledon described a generalization of Ehrhart theory with group actions. In 2018, Ardila, Schindler, and I made progress towards answering one of Stapledon�s open problems that asked to determine the equivariant Ehrhart theory of the permutahedron. We proved some general results about the fixed polytopes of the permutahedron, which are the polytopes that are fixed by acting on the permutahedron by a permutation. In particular, we computed their dimension, showed that they are combinatorially equivalent to permutahedra, provided hyperplane and vertex descriptions, and proved that they are zonotopes. Lastly, we obtained a formula for the volume of these fixed polytopes, which is a generalization of Richard Stanley?s result of the volume for the standard permutahedron. Building off of the work of the aforementioned, we determine the equivariant Ehrhart theory of the permutahedron, thereby resolving the open problem. This project presents combinatorial formulas for the Ehrhart quasipolynomials and Ehrhart Series of the fixed polytopes of the permutahedron, along with other results regarding interpretations of the equivariant analogue of the Ehrhart series. This is joint work with Federico Ardila (San Francisco State University) and Mariel Supina (UC Berkeley).

Since the beginning of tropical geometry, a persistent challenge has been to emulate tropical versions of classical results in algebraic geometry. The well-known statement "any smooth surface of degree three in P^3 contains exactly 27 lines'' is known to be false tropically. Work of Vigeland from 2007 provides examples of tropical cubic surfaces with infinitely many lines and gives a classification of tropical lines on general smooth tropical surfaces in TP^3.
In this talk I will explain how to correct this pathology by viewing the surface as a del Pezzo cubic and considering its embedding in P^44 via its anticanonical bundle. The combinatorics of the root system of type E_6 and a tropical notion of convexity will play a central role in the construction. This is joint work with Anand Deopurkar (arXiv: 1906.08196).

Enumerative algebraic geometry counts the solutions to certain geometric constraints. Numerical nonlinear algebra determines these solutions for any given instance. This talk illustrates how these two fields complement each other, especially in the light of emerging new applications. We start with a wonderful piece of 19th century geometry, namely the 3264 conics that are tangent to five given conics in the plane. Thereafter we turn to current problems in statistics and data science, with focus on the maximum likelihood estimation for linear Gaussian covariance models.

Symbolic computations based on Gr�bner basis are widely used, with great success, to compute several algebraic invariants. Nevertheless, such symbolic computations are expensive in time. Numerical Algebraic Geometry, an emerging field, specialises algorithms form Numerical Analysis to work on polynomial systems defined over the complex numbers, improving its performance by means of Algebraic Geometry. In this talk, we will outline an algorithm to compute the local dimension of an algebraic set.

We determine the 166104 extremal monomials of the discriminant of a quaternary cubic form. These are in bijection with D-equivalence classes of regular triangulations of the 3-dilated tetrahedron. We describe how to compute these triangulations and their D-equivalence classes in order to arrive at our main result. The computation poses several challenges, such as dealing with the sheer amount of triangulations effectively, as well as devising a suitably fast algorithm for computation of a D-equivalence class.

Constructing moduli spaces is a fundamental problem in algebraic geometry. In this context, the stability of an object determines whether or not it fits into a moduli space and often becomes an important notion in its own right (for example stable sheaves and stable curves). The moduli of hypersurfaces in toric varieties is constructed using geometric invariant theory and an analysis of stability using the Newton polytope uncovers discrete geometry as a powerful tool to study the moduli of such hypersurfaces. In this talk we show how one relates stability of hypersurfaces and certain discrete geometric conditions on their Newton Polytopes.

I will give a short talk about the recent Summer School at MPI Leipzig on Randomness and Learning in Non-Linear Algebra. I will focus particularly on models of random monomial ideals and their connections with random graphs and simplicial complexes.

This talk is a follow-up on Guillermo Pineda's previous DMG talk: "Minkowski decompositions of polytopes via geometric graphs". In his work (Pineda-Villacicencio et al (2018)), there is an example of a 3-dimensional polytope that admits both a decomposable (i.e.: Minkowski sum of non-homothetic polytopes) realisation and a indecomposable realisation. This shows that decomposability of polytopes cannot be decided by the combinatorics alone. In this talk, we will show why his example does not extend to higher dimensions.

The celebrated Bohne-Dress theorem characterizes tilings of a given zonotope $\mathcal{Z}$ by zonotopes in terms of single-element liftings of the oriented matroid associated to $\mathcal{Z}$. In this talk I will show how one might prove this result using a certain reinterpretation of the chirotope of an oriented matroid. I will also discuss several related open questions.

The single-source unsplittable flow problem has been introduced by Kleinberg (1996) and generalizes several NP-complete problems from various areas in combinatorial optimization such as packing, partitioning, scheduling and load balancing. Commodities must be routed simultaneously in a given arc-capacitated graph. Each of the commodities has a common source, a destination and a requested flow demand. The problem consists in routing each commodity through a single path without violating the given arc capacities.
Twenty years ago, in a landmark paper, Dinitz, Garg and Goemans proved that any multiple-path routing can be turned into a single-path routing with an increase of flow on each arc bounded by the value of the maximum demand. In the first part of the talk, we present a completely new and considerably simpler proof for this result, with the goal of making progress towards the related but still unresolved Conjecture of Goemans for minimum-cost unsplittable flows. In the second part of the talk, we focus on known relations between the single-source unsplittable flow problem and polytopes.
This is joint work with Martin Skutella.

TBA

Covering minima of a convex body were introduced by Kannan and Lovasz to give a better bound on the constant in the flatness theorem, which states that the width of hollow convex bodies in a fixed dimension is bounded by a constant. These minima are similar in flavor to Minkowski's successive minima, and on the other hand generalize the covering radius of a convex body. I will speak about recent joint work with Francisco Santos and Matthias Schymura, where we investigate extremal values of these covering minima for non-hollow lattice polytopes.

A tropical line on a smooth tropical cubic surface can be realised, if there exists a line on a smooth cubic surface, such that the tropicalisation of the surface and the line coincide with the given tropical cubic surface and tropical line. (This is called relative realisability.)
The tropical lines on a smooth tropical cubic surface can be classified by their combinatorial position. Thus we can distinguish isolated lines and two-point families. The latter are infinite families of tropical lines on the same surface of the same combinatorial position. There are two combinatorial positions of lines of general smooth tropical cubic surfaces that allow infinite families. The question is, whether all the lines in these families can be realised on some lift of the tropical cubic surface. This problem is only solved for one of the two positions and only if char(k)?2 I will present the solution.

In this talk, we study the persistent homology and related geometric properties of the evolution in time of a discrete-time stochastic process defined on the 2-dimensional regular square lattice. This process corresponds to a cell growth model called the Eden Growth Model (EGM). It can be described as follows: start with the cell square of the 2-dimensional regular square lattice of the plane that contains the origin; then make the cell structure grow by adding one cell at each time uniformly random to the perimeter. We give a characterization of the possible change in the rank of the first homology group of this process (the "number of holes"). Based on this result we have designed and implemented a new algorithm that computes the persistent homology associated to this stochastic process and that also keeps track of geometric features related to the homology. Also, we present obtained results of computational experiments performed with this algorithm, and we establish conjectures about the asymptotic behavior of the homology and other related geometric random variables. The EGM can be seen as a First Passage Percolation model after a proper time-scaling. This is the first time that tools and techniques from stochastic topology and topological data analysis are used to measure the evolution of the topology of the EGM and in general in FPP models.

Eble: Epistatic weights and cluster filtrations provide a mathematical tool for studying biological data sets. In this informal talk I will present the geometric motivation behind these notions.
Tewari: In the paper 'Moduli of tropical plane curves Brodsky', etc (2015) compute the moduli space of tropical curves of genus g, with g = 3, 4 and 5. In this talk, we would delve into computations trying to extend that computation to the case of g = 6.

We study the class of nonnegative polynomials obtained from the inequality of arithmetic and geometric means, called \emph{agiforms} or \emph{nonnegative circuit polynomials}. They generate a full dimensional subcone $S$ of the cone of all nonnegative polynomials, which is distinct from the cone of sums of squares. Let $\mathbb{R}^A$ denote the space of all real polynomials with support $A$. We describe the boundary of the cone $S \cap \mathbb{R}^A$ as a space stratified in real semi-algebraic varieties. In order to describe the strata, we take a journey through discriminants, polytopes, and triangulations, oriented matroids, and tropical geometry. Based on joint work with Timo de Wolff.

It will be shown how, using the homogeneous contour integral, information theoretic invariants and inequalities involving entropy, moments, Fisher information can be translated into convex geometric invariants and inequalities.

Much attention has been focused in recent years on the following algebraic problem arising from applications: which chemical reaction networks, when taken with mass-action kinetics, admit multiple positive steady states? The interest behind this question is in steady states that are stable. As a step toward this difficult question, here we address the question of multiple nondegenerate positive steady states. Mathematically, this asks whether certain families of parametrized, real, sparse polynomial systems ever admit multiple positive real roots that are simple. Our main results settle this problem for certain types of small networks, and our techniques point the way forward for larger networks. This is joint work with Anne Shiu.

Toric Fano varieties are in one to one correspondence to so called Fano polytopes. The lattice points in the Fano polytope determine the singularity type of the corresponding toric Fano variety and thus allows classification with purely combinatorial methods. For varieties with a torus action of complexity one, i.e. the general torus orbit is of dimension one less than the dimension of the variety, the anticanonical complex has been introduced as a natural generalisation of the toric Fano polytope. We give a sufficient condition on Fano varieties with torus action of arbitrary complexity that admit an anticanonical complex, i.e. a polyhedral complex whose lattice points determine their singularity type. We show that the possibility to apply the anticanonical complex to these varieties is connected to certain properties of their quotients and use this fact to construct first example classes.

In this talk we will present some recent results on the distance from a vertex of an integer feasible knapsack polyhedron \(P\) to its nearest lattice point in \(P\) (referred to as a vertex distance). We give a sharp upper bound for the vertex distance that only depends on the maximum norm of the vector \(a\). In a randomised setting, we show that the vertex distance for a typical knapsack polyhedron is drastically smaller than the vertex distance that occurs in a worst case scenario. This is a joint work with Martin Henk and Timm Oertel.

In this survey talk we will introduce p-adic fields and more generally non-archimedean valued fields. We will point out that the topology induced by the absolute value is totally disconnected. This make it more difficult to define manifolds and geometric theories over these fields. We will see how Berkovich's approach of analytic spaces deal with these problems.

We will study the interactions of combinatorics and geometry via cluster algebras. We will begin with the simple case of the Grassmannians Gr(2,n), where this connection is completely determined by the type A_n associahedron, corresponding to triangulations of an n+3-gon. Next, we will discuss the case for general Gr(k,n) and the Lagrangian Grassmannians LG(n), where will focus on combinatorial objects called plabic graphs. We will discuss how the cluster structure in these cases gives a method to understand the Newton-Okounkov bodies of these varieties, and give a connection to Khovanskii bases and toric degenerations. Time permitting, we will also the study relation to the tropical Grassmannians and positivity.

The underlying theme of the talk is the reduction of the (hard analytic) ques- tion of Kazhdan�s property (T) to an (algebraic, computable) problem of non- commutative optimisation. In this formulation, property (T) is equivalent to the positivity of the element ? 2 ? ? ? in (full) C * -group algebra (where ? is the group Laplacian). This problem will serve as a motivation to explore the topic of non-commutative positivity. I will present certain results on positivity for free * -algebras and group al- gebras. It turns out that, due to much richer representation theory of non- commutative objects, the Positivestellens�tze in the non-commutative world are much stronger than in the commutative world: the positive cone is in many cases equal to the cone of sums of (hermitian) squares. Moreover one of the characterisations of cones in the �algebraic topology� of * -algebra allows turning a numerical approximation of the the sum of squares decomposition (of ? 2 ? ? ? ) into a mathematical proof of the positivity. I will finish by presenting the very concrete case of the application of the theory to S Aut( F n ), the (special) automorphism group of the free group on five generators. Using Gramm method we formulated The successful execution of the described programme was obstructed by the sheer size of the optimisation problem. To overcome these difficulties we exploited the symmetry of ? 2 ? ? ? and used the theory of representations of finite groups to significantly reduce the complexity of the optimisation problem, wich might be of interest of its own.

Polynomial instances of hypergeometric functions in one and several variables are very diverse. They comprise the classical Chebyshev polynomials of the first and the second kind, the Gegenbauer, Hermite, Jacobi, Laguerre and Legendre polynomials as well as their numerous multivariate analogues.
Despite the diversity of families of hypergeometric polynomials, most of them share the following key properties that justify the usage of the term "hypergeometric":
1. The polynomials are dense (possibly after a suitable monomial change of variables).
2. The coefficients of a hypergeometric polynomial are related through some recursion with polynomial coefficients.
3. For univariate polynomials, there is typically a single representative (up to a suitable normalization) of a given degree within a family of hypergeometric polynomials.
4. All polynomials in the family satisfy a differential equation of a fixed order with polynomial coefficients (or a system of such equations) whose parameters encode the degree of a polynomial.
5. In the case of one dimension, the absolute values of the roots of a classical hypergeometric polynomial are all different (possibly after a suitable monomial change of variables).
6. Many of hypergeometric polynomials enjoy various extremal properties.
In the talk, we will introduce a definition of a multivariate hypergeometric polynomial in several complex variables that is coherent with the properties 1-6 listed above. Namely, with any integer convex polytope P we associate a multivariate hypergeometric polynomial whose set of exponents is P.
The hypergeometric polynomial associated with the polytope P is defined uniquely up to a constant multiple and satisfies a holonomic system of partial differential equations of Horn's type. We prove that under certain nondegeneracy conditions the zero locus of any such polynomial is optimal in the sense of Forsberg-Passare-Tsikh. Generally speaking, this means that the topology of the amoeba of such a polynomial is as complicated as it could possibly be. This property is the multivariate counterpart of the property of having different absolute values of the roots for a polynomial in a single variable.

Through the process of tropicalization one obtains from an algebraic variety $X$ a combinatorial object called the tropicalization of $X$, $trop(X)$, that retains a lot of information about the original variety. Following the work of J. Giansiracusa and N. Giansiracusa, one can endow $trop(X)$ with more structure, to obtain a tropical scheme. Loosely speaking, we consider more equations than the ones needed to determine the tropical variety. We are interested what information about the original variety $X$ is preserved by the tropical scheme $X_\mathbb{T}$ (but possibly not by the tropical variety). In particular, we study the relation between the Picard group of $X$ and $X_\mathbb{T}$. We solve the problem in the case when $X$ is a toric variety.

It is due to Blekherman that we now know there are significantly more nonnegative forms than sums of squares for any fixed degree \(2d\) and large number of variables \(n\). What if we ask the same comparison for polynomials with a prescribed Newton polytope? I will present some general ideas from (modern) convex geometry that handles the case of multihomogeneous polynomials. These results refine the estimates of Blekherman and happens to have some implications in quantum information theory. I will also try to indicate missing ingredient(s) for handling general Newton polytopes, which might be of interest to the lovers of toric geometry and/or Lie algebras.

I will discuss some methods/techniques to prove "small ball probabilities" and I will review some connections with other problems in Asymptotic Geometric Analysis. The emphasis will be on how high-dimensional geometry and convexity is crucial to understand the concentration behavior in the "small ball regime".

An affine semigroup \(S\) is a subset of \(\mathbb Z_{\ge 0}^k\) that is closed under vector addition, and a factorization of \(a \in S\) is an expression of \(a\) as a sum of generators of \(S\). The delta set of \(a\) is a set of positive integers determined by the 'missing factorization lengths' of \(a\), and the delta set of \(S\) is the union of the delta sets of its elements. Although the delta set of any affine semigroup is finite, its definition as an infinite union makes explicit computation difficult. In this talk, we explore algebraic and geometric properties of the delta set, and survey the history of its computation for affine semigroups. The results presented here span the last 20 years, ranging from a first algorithm for a small class of semigroups that is impractical for even basic examples, to recent joint work with Garcia-Sanchez and Webb expressing the delta set of any affine semigroup in terms of Groebner bases, and include results from numerous undergraduate research projects.

To compute certificates of nonnegativity, an approach based on sums of squares (SOS) decompositions has been popularized by Lasserre and Parillo.
In the first part of this talk, we consider the problem of finding SOS decompositions of nonnegative univariate polynomials. It is well-known that every non-negative univariate real polynomial can be written as the sum of two polynomial squares with real coefficients. When one allows a weighted sum of finitely many squares instead of a sum of two squares, then one can choose all coefficients in the representation to lie in the field generated by the coefficients of the polynomial. We describe, analyze and compare two algorithms computing such a weighted sums of squares decomposition for univariate polynomials with rational coefficients. - The first algorithm, due to Schweighofer, relies on real root isolation, quadratic approximations of positive polynomials and square-free decomposition but its complexity was not analyzed. We provide bit complexity estimates, both on runtime and output size of this algorithm. They are exponential in the degree of the input univariate polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using quantifier elimination and root isolation bounds. - The second algorithm, due to Chevillard, Harrison, Joldes and Lauter, relies on complex root isolation and square-free decomposition and has been introduced for certifying positiveness of polynomials in the context of computer arithmetics. Again, its complexity was not analyzed. We provide bit complexity estimates, both on runtime and output size of this algorithm, which are polynomial in the degree of the input polynomial and linear in the maximum bitsize of its complexity. This analysis is obtained using Vieta's formula and root isolation bounds. While the second algorithm is, as expected from the complexity result, more efficient on most of examples, we exhibit families of non-negative polynomials for which the first algorithm is better.
In the second part of this talk, we consider the problem of finding exact sums of squares (SOS) decompositions for certain classes of nonnegative multivariate polynomials, while relying on semidefinite programming (SDP) solvers. - We start by providing a hybrid symbolic-numeric algorithm computing exact rational SOS decompositions for polynomials lying in the interior of the SOS cone. This algorithm computes an approximate SOS decomposition for a perturbation of the input polynomial with an arbitrary-precision SDP solver. An exact SOS decomposition is obtained thanks to the perturbation terms. We prove that bit complexity estimates on output size and runtime are both polynomial in the degree of the input polynomial and simply exponential in the number of variables. This analysis is based on quantifier elimination as well as bounds on the cost of the ellipsoid method and Cholesky's decomposition. - Next, we apply this algorithm to compute exact Polya and Putinar's representations respectively for positive definite forms and polynomials positive over basic compact semialgebraic sets. We compare the implementation of our algorithms with existing methods based on CAD or critical points.
This is joint work with Mohab Safey El Din and Markus Schweighofer.

Buildings form a fundamental geometric concept which generalize the Coxeter complex of a Coxeter group. The theory was mostly developed by Tits (and Borel) in the 1960s and 1970s. While its origins are in Lie theory one particularly striking application was its contribution to the classification of the finite simple groups (completed around 1980). In this talk (of historical survey type) I will define the three notions in the title and look into one family of examples. In the end I will briefly try to sketch the impact on group theory in general.

Constructing efficient algorithms for combinatorial optimization problems is a task that requires a lot of knowledge, experience and creativity. The goal of this talk is to present the automatizable hierarchies of algorithms (Lasserre/Sum-of-Squares (SoS), Sherali Adams (SA)) and the recent development in this field, the Sum-of-Nonnegative-Circuit (SoNC) algorithm.
We start with a motivation and a gentle introduction to the hierarchies of relaxations for 0/1 optimization problems. Next we discuss the strength and weaknesses of this approach and present a novel method in this field, the SoNC hierarchy.
Finally, in this talk we show that key results for SOS/SA hierarchy remain valid for SoNC hierarchy. More precisely we show that for a polynomial optimization problem over the $n$-variate boolean hypercube with constraints of degree $d$, the SoNC hierarchy at level $n+d$ converges to the convex hull of integral solutions.

Fuglede's conjecture (1974) states that a bounded measurable subset in \(\mathbb{R}^d\) accepts an orthogonal basis of exponential functions (i.e. it is spectral) if and only if it tiles the space with a discrete set of translations. This conjecture turned out to be false by Tao's counterexample in 2003. Using Tao's ideas, counterexamples in finite Abelian groups such as \(\mathbb{Z}_N^d\) can be lifted to counterexamples in \(\mathbb{R}^d\), thus shifting the interest on this conjecture to this setting in recent years. This has been successful for \(d\geq3\), but the conjecture is still open for \(d=1,2\).
Some recent results in the cyclic group setting will be presented in this talk, which are connected to the work of Coven-Meyerowitz and Laba on tiling subsets of \(\mathbb{Z}\), as well as the structure of vanishing sums of roots of unity. This is joint work with Mihalis Kolountzakis & work in progress.

In this talk we explain how every even, zonal measure on the Euclidean unit sphere gives rise to a sharp Sobolev inequality for functions of bounded variation which directly implies the classical Euclidean Sobolev inequality. The strongest member of this large family of inequalities is shown to be the only affine invariant one among them � the affine Zhang-Sobolev inequality. We discuss in some detail the geometry behind these analytic inequalities and also relate our new Sobolev inequalities to the sharp Gromov-Gagliardo-Nirenberg Sobolev inequality for general norms and discuss further improvements of special cases.

Moment-sum-of-squares hierarchies of semidefinite programs can be used to approximate the volume of a given compact basic semialgebraic set K. The idea consists of approximating from above the indicator function of K with a sequence of polynomials of increasing degree d, so that the integrals of these polynomials generate a convergence sequence of upper bounds on the volume of K. In this talk we show how we could derive an asymptotic rate of convergence for this approximation scheme. Joint work with Milan Korda, see arXiv:1609.02762.

In this talk we present the SoS hierarchy in the context of 0/1 optimization along with some of our recent integrality gap/lower bound results. We introduce the relevant concepts and give a brief derivation of the hierarchy. As for our results, we characterize the possible gap instances on the round n-1 of the hierarchy. Then we show an unbounded integrality gap after nonconstant number of rounds for a problem that admits a polynomial time algorithm. Finally we present a simplification of the positive semidefiniteness constraints when a high degree of symmetry can be assumed, and some applications to integrality gaps and lower Bounds.

We present structural results on sparse nonnegative integer solutions to underdetermined systems of linear equations.
Our proofs are algebraic and number theoretic in nature and make use of Siegel's Lemma and classical tools from the Geometry of Numbers.
These results have some interesting consequences in discrete optimisation.

In this talk we will present algorithms to check smoothness for the class of spherical varieties which contains those of toric varieties, flag varieties and symmetric varieties, and which forms a remarkable class of algebraic varieties with an action by an algebraic group having an open dense orbit. In the toric case there is a well-known simple combinatorial smoothness criterion whereas in the spherical case Brion, Camus and Gagliardi have shown smoothness criteria for spherical varieties which either are rather involved or rely on certain classification results. We suggest a purely combinatorial smoothness criterion by introducing a rational invariant which only depends on the combinatorics of the spherical variety. We have a conjectural inequality this invariant should satisfy where the equality case would imply that the spherical variety has a toric torus action. Our conjecture would also imply the generalized Mukai conjecture for spherical varieties. We complete our talk by summarizing in which cases the above mentioned approach is known to be true. This is joint work with Giuliano Gagliardi.

Given \(k\in \mathbb{R}_{\ge 0}\) and a vector \(v\) of Plücker coordinates of a point in the real Grassmannian, is the vector obtained by taking the \(k\)th power of each entry of \(v\) again a vector of Plücker coordinates? We will show that for \(k\neq 1\), this is true if and only if the corresponding matroid is regular. Similar results hold over other fields. We will also describe the subvariety of the Grassmannian that consists of all the points that define a regular matroid.
An arithmetic matroid is a matroid equipped with a function that assigns a multiplicity (a positive integer) to each subset of the ground set. We will discuss a discrete version of the problem described above that deals with the representability of the arithmetic matroid obtained by taking the \(k\)th power of the multiplicity function. This setting is motivated by some combinatorial questions on CW complexes.

We live in the age of data, huge amount of Data its been generated and acquired everyday in different forms and flavors. One would like to have a technique to store and process optimally this data; this is possible since the relevant information in almost all data found in typical applications is sparse due the high correlation of its elements. The challenge will lie in the search of appropriate dictionary that can represent optimally this information. Along the history very talented scientist have proposed different signal transforms based on certain representation dictionaries, starting with the Fourier Transform and Short Time Fourier Transform; in 1980s the wavelet transform was proposed representing a breakthrough in one dimensional signal representation, with the ability to not just optimally represent the data but also capture certain singularities, regularities and other features; the flaw of the wavelets transforms is its lack of directional sensitivity which does not aloud it to represent optimally multidimensional singularities like curves that are predominant in general multidimensional signals (for instance images and videos). The Shearlet transform is a product of almost 10 years of research on sparsifying transform with directional sensitivity that attains the optimal best N-term approximation error, it was proposed by G. Kutyniok, D. Labate and K Guo in 2015 and since then it's been known to be the best of its type.
In this talk I will explain the upsides and downsides of the already mentioned transforms, why the shearlet transform is great solution for anisotropic representation of multidimensional signals, how can we implement wavelet and shearlet transform in Julia, and I will show you some applications and demos of the Shearlet Transform Library that I implemented with Professor Gitta Kutyniok based on the matlab version developed by her group two years ago; I will also explain why Julia is the best option to implement algorithms in Signal and Image Processing and show some benchmarks that show its great performance.

A family \(\mathcal{F}\) of sets is in convex position if none of its members is contained in the convex hull of the union of the others. The members of \(\mathcal{F}\) are ovals (compact convex sets) in the plane that have a certain property. An Erdos-Szekeres type theorem concerns the existence, for any integer \(n\geq 3\), of a smallest positive integer \(N(n)\) such that if \(|\mathcal{F}|?N(n)\) then there are \(n\) ovals of \(\mathcal{F}\) in convex position.
In this talk, I survey some known theorems, introduce a new one based upon work with Gabor Fejes Toth and examine the relation between \(N(n)\) and Ramsey numbers of the type \(R_k(n_1,n_2)\).

This talk will focus on open problems in Geometric Tomography, which aims to retrieve information about a geometric object (such as a convex body, star body, finite set, etc.) from data concerning its intersections with planes or lines and/or projections (i.e., shadows) on planes or lines. The problems, which span nearly a hundred years of mathematics, are diverse. Many have a common thread, however, since they are linked to various integral transforms: the X-ray transform, divergent beam transform, circular Radon transform, cosine transform, or spherical Radon transform.
The talk will be illustrated by plenty of pictures.

Numerical computations by Cohn, Kumar, and Schu?rmann in energy minimizing periodic configurations of density \(\rho\) and \(1/\rho\) revealed an impressive kind of symmetry, the so�called formal duality. Formal dual subsets of \(\mathbb{R}^n\) satisfy a generalized version of Poisson summation formula, and it is conjectured that the only periodic subsets of \(\mathbb{R}\) of density \(1\) possessing a formal dual subset, are \(\mathbb{Z}\) and \(2\mathbb{Z}\cup(2\mathbb{Z}+\frac12)\).
In this talk, we will present recent progress on this conjecture by the speaker, utilizing several tools from different areas of mathematics, such as (a) the field descent method by Bernhard Schmidt, used chiefly on the circulant Hadamard matrix conjecture, (b) the 'polynomial method' by Coven & Meyerowitz used in the characterization of sets tiling \(\mathbb{Z}\) or \(\mathbb{Z}_N\), and (c) basic arithmetic of cyclotomic fields.

We introduce mplrs, a new parallel vertex/facet enumeration program based on the reverse-search code lrs. The implementation uses MPI and can be used on single machines, clusters and supercomputers. We describe the budgeted parallel tree search implemented in mplrs and compare performance with other sequential and parallel programs for vertex/facet enumeration. In some instances, mplrs achieves almost linear scaling with more than 1000 cores. The approach used in mplrs can be easily applied to various other problems. This is joint work with David Avis.

A lattice polytope is a convex polytope each of whose vertices has integer coordinates. It is known that a lattice simplex of dimension \(d\) corresponds to a finite abelian subgroup of \((\mathcal{R}/\mathcal{Z})^{d+1}\). Conversely, given a finite abelian subgroup of \((\mathcal{R}/\mathcal{Z})^{d+1}\) such that the sum of all entries of each element is an integer, we can obtain a lattice simplex of dimension \(d\). In this talk, we discuss a characterization of Gorenstein simplices in terms of the associated finite abelian groups. Gorenstein polytopes are of interest in combinatorial commutative algebra, mirror symmetry and tropical geometry. In particular, we present complete characterizations of Gorenstein simplices whose normalized volume equal \(p\), \(p^2\) and \(pq\), where \(p,q\) are prime integers.

Although hyperplane arrangement complements are rationally formal, we note that they have non-minimal rational (CDGA) models which are topologically and combinatorially significant. We construct a family of CDGAs which interpolates between the Orlik-Solomon algebra and the cohomology algebras of arrangement compactifications. Our construction is combinatorial and extends to all matroids, regardless of their (complex) realizability.
This is joint work with Christin Bibby and Graham Denham.

I present the recent work 'Slicing and dicing polytopes' (arXiv:1608.05372) by Patrik Nor�n on cellular resolutions. I introduce diced and sharp polytopes which are necessary for the construction and give a brief introduction to cellular resolutions. The main result, introducing a new class of polyhedral subdivisions which support cellular resolutions, is illustrated along some examples.

By studying the volume of a generalized difference body, this talk presents the first nontrivial lower bound for the lattice covering density by \(n\)-dimensional simplices.

tba

A classification of symmetric tensor valuations on lattice polytopes in \(\mathbb{R}^n\) that intertwine the special linear group over the integers is established for the cases in which the rank of the tensor is at most \(n\). The scalar-valued case was classified by Betke and Kneser where it was shown that the only such valuations are the coefficients of the Ehrhart polynomial. Extending this result, the coefficients of the discrete moment tensor form a basis for the symmetric tensor valuations.

The Hardy constant of a simply connected domain \(\Omega\subset\mathbb{R}^2\) is the best constant for the inequality \[ \int_\Omega |\nabla u|^2 dx \geq c\int_\Omega \frac{u^2}{\operatorname{dist}(x,\partial\Omega)^2} dx, \quad u\in C_c^\infty(\Omega). \] After the work of Ancona where the universal lower bound 1/16 was obtained, there has been a substantial interest on computing or estimating the Hardy constant of planar domains. In this talk we determine the Hardy constant of an arbitrary quadrilateral as well as of some other planar domains (joint work with Achilles Tertikas).

The main aim of compressed sensing is to recover a low-dimensional object (e.g. a sparse vector, a low-rank matrix, ...) from few linear measurements. Many algorithms for this task (e.g. Basis Pursuit, nuclear norm-minimization) consists of minimizing a structure-promoting function \(f\) over the set of possible solutions.

An elegant approach to finding recovery guarantees of such programs relies on high-dimensional geometry of convex cones. The techniques were developed relatively recently, but have quickly gained popularity. In the first half of this talk, this approach will be presented in relative high detail.

In the second half of the talk, we will discuss the connection between geometry and stability of compressed sensing algorithms. In particular, we will present a new geometric criterion on \(A\) implying stability both with respect to model inexactness of the signal as well as to additive noise in the measurements.

The spectral theory of tensors aims at generalizing the concept of eigenvalues and eigenvectors of matrices to higher dimensional arrays. In this talk I will focus on the definition of E-eigenvalues and Z-eigenvalues given by Qi. After giving the definition itself I will explain various applications, give the higher dimensional equivalent of the characteristic polynomial and talk about the number of eigenvalues of both real and complex tensors. The last part of the talk will be about an algorithm to compute eigenvalues of tensors using homotopy methods and the complexity of this algorithm.

Given a subset S of R^n, let c(S,k) be the smallest number t such that whenever finitely many convex sets have exactly k common points in S, there exist at most t of these sets that already have exactly k common points in S. For S = Z^n, this number was introduced by Aliev et al. [2014] who gave an explicit bound showing that c(Z^n,k) = O(k) holds for every fixed n. Recently, Chestnut et al. [2015] improved this to c(Z^n,k) = O(k (log log k)(log k)^{-1/3} ) and provided the lower bound c(Z^n,k) = Omega(k^{(n-1)/(n+1)}). We provide a combinatorial description of c(S,k) in terms of polytopes with vertices in S and use it to improve the previously known bounds as follows: We strengthen the bound of Aliev et al. [2014] by a constant factor and extend it to general discrete sets S. We close the gap for Z^n by showing that c(Z^n,k) = Theta(k^{(n-1)/(n+1)}) holds for every fixed n. Finally, we determine the exact values of c(Z^n,k) for all k <= 4.

In this talk, we study the problem of estimating a structured signal \(x_0\in\mathbb{R}\) linear Gaussian observations. Supposing that \(x_0\) belongs to a certain convex subset \(K\subset\mathbb{R}\) we will see that an accurate recovery is possible as long as the number of observations exceeds the effective dimension of \(K\), which is a common measure for the complexity of signal classes. Interestingly, it will turn out that the (possibly unknown) non-linearity of our model affects the error rate only by a multiplicative constant. This achievement is based on recent works by Yaniv Plan and Roman Vershynin, who have suggested to treat the non-linearity rather as noise which perturbs a linear measurement process. Using the concept of restricted strong convexity, we show that their results for the generalized Lasso can be extended to a fairly large class of convex loss functions. This is especially appealing for practical applications, since in many real-world scenarios, adapted loss functions empirically perform better than the classical square loss. To this end, the presented results provide a unified and general framework for signal reconstruction in high dimensions, covering various challenges from the fields of compressed sensing, signal processing, and statistical learning.

This talk is a summary of the very recent paper by Matthew Baker of the same title (http://arxiv.org/pdf/1601.01204.pdf). Various flavours of ''matroids with additional structure'', such as valuated and oriented matroids have been around for quite a while, with often very little connection between the different matroid species. Matroids over hyperfields are a generalization of all those concepts - thus allowing a unified treatment. In this talk I will first give a short introduction to hyperfields. I will then define what matroids over hyperfields are, give examples and discuss generalizations of familiar matroid operations such as duality and minors.

Wished for by Weil and defined by Grothendieck, �tale cohomology is to varieties over fields of finite characteristic what usual cohomology is to complex or real algebraic varieties when they are equipped with the analytic, respectively Euclidean topology. This very short introduction will motivate and try to explain the basic ingredients of �tale cohomology. Throughout I will make analogies to the complex and real situations and stick to simple examples in hopes to provide some intuition into this deep theory.

The Minkowski measure of symmetry s(K) of a convex body K, is the smallest positive dilatation of K containing a translate of -K. In this talk we will explain some of its basic properties in detail.

Afterwards, we will show how s(.) can be used to strengthen, smoothen, and join different geometric inequalities, as well as its connections to other concepts such as diametrical compleness, Jung's inequality, or Banach-Mazur distance.

The Turaev-Viro invariants are a powerful family of topological invariants for distinguishing between different 3-manifolds. They are invaluable for mathematical software, but current algorithms to compute them require exponential time. I will discuss this family of invariants, and present an explicit fixed-parameter tractable algorithm for arbitrary r which is practical -- and indeed preferable -- to the prior state of the art for real computation.
This is joint work with Ben Burton and Clément Maria