SS 2022

Freitag, 22. April 2022 um 13:30 – 15:00 Uhr, Oberseminar Relle Geometrie und Algebra

Luis Vargas (CWI Amsterdam)

(Gast von Markus Schweighofer)

The stability number of a graph and sums of squares of polynomials

Given a graph G, its stability number is the cardinality of the largest subset of vertices without edges between them. Computing the stability number is an NP-hard problem and some approximations via semidefinite optimization, have been developed. One of them is a hierarchy proposed by de Klerk and Pasechnik by following an idea given by Parrilo for approximating problems over the copositive cone via sums of squares of polynomials. One open question asks for the finite convergence of this hierarchy. We prove finite convergence for the class of graphs without critical edges. Our analysis relies on exploiting a link to the Lasserre hierarchy for the Motzkin-Straus formulation and using a known sufficient condition for its finite convergence. As an application we can show that deciding whether a standard quadratic problem has finitely many global minimizers is hard.

Montag, 25.April 2021 um 15:15 Uhr, Logic Colloquium

Tobias Sutter (University of Konstanz)

(Gast von Salma Kuhlmann and Carolin Antos-Kuby)

From Machine learning to topological linear system identification

Given the recent progress in information technology with real-time data
being available at large scale, many complex tasks involving dynamical environments are addressed via tools from machine learning, control theory and optimization. While control theory in the past has mainly focused on model based design the advent of large scale data sets raises the possibility to analyse dynamical systems on the basis of data rather than analytical models. From a machine learning perspective, one of the main challenges going forward is to tackle problems involving dynamical systems which are beyond static pattern recognition problems. In this talk, I will give an overview about different problems lying in this intersection of dynamical systems, learning and control that I have worked on in the past. In particular, I will discuss how to efficiently learn a linear dynamical system with stability guarantees and how to identify its topological equivalence class based on a single trajectory of correlated data.

Montag, 2.Mai 2021 um 15:15 Uhr, Oberseminar Complexity Theory, Model Theory, Set Theory.

Leonid Monin (MPI Leipzig)

(Gast von Mateusz Michalek and Salma Kuhlmann)

Number of roots of systems of polynomial equations

My talk will be dedicated to the famous BKK (Bernstein-Kouchnireno-Khovanskii) theorem which computes the number of solutions of a system of Laurent polynomials in terms of volumes of certain polytopes. BKK theorem has at least a dozen different proofs, most of which lead to a far reaching generalisations of BKK theorem. In my talk I will focus on two different ideas of the proof: one leading to the theory of Newton-Okounkov bodies and the other leading to the tropical geometry. If time permits, I will also mention my own work on overdetermined systems of equations.

Freitag, 06. Mai 2022 um 13:30 – 15:00 Uhr, Oberseminar Relle Geometrie und Algebra

Andreas Kretschmer(OVGU Magdeburg)

(Gast von Mateusz Michalek)

How many cubic surfaces are tangent to 19 general lines?

In this talk I will survey the construction of a so-called
1-complete variety of cubic hypersurfaces, generalizing Aluffi's
variety of complete plane cubic curves to higher dimensions. The aim
is to answer the question posed in the title and more of a similar
flavor, and to give an intuitive geometric meaning to the "exceptional
points" of our 1-complete variety of cubic hypersurfaces.

Montag, 16.Mai 2021 um 15:15 Uhr, Logic Colloquium

Salvador Mascarenhas (Ecole Normale Supérieure)

(Gast von Salma Kuhlmann and Carolin Antos-Kuby)

In a range of probabilistic reasoning tasks, humans seemingly fail to
choose the option with the highest posterior probability (i.e. the highest chance of being true). For example, in their seminal 1973 article, Kahneman and Tversky presented human participants with descriptions of individuals, and observed that participants produced judgments of the probability that those individuals belonged to one of two professions (lawyers vs. engineers) while seemingly ignoring the prior probabilities of those two categories in the sample at hand. One family of theories hold that human reasoners in such decision tasks ask themselves to what extent a piece of information supports a particular conclusion (Crupi et al. 2008, Tentori et al. 2013). In this view, participants ignore prior probabilities in the lawyers-engineers paradigm because they are interested in the extent to which the description supports a lawyer or an engineer hypothesis, regardless of prior probabilities. This confirmation-theoretic view has been extremely successful at modeling human behavior in many probabilistic reasoning tasks, and it has been applied to recalcitrant fallacies from deductive reasoning (Sabl ́e-Meyer & Mascarenhas, 2021). Yet, a justification for it is lacking to this day. That is, however rational (Bayesian) confirmation-theoretic strategies might be as means of assessing the extent to which some evidence supports a hypothesis, it is an open question why humans would engage in such a process, when at least at first blush the most rational strategy in a decision task of this kind is to identify the option with the highest posterior probability, which entails taking prior probabilities into account. In this talk, I propose that confirmation-theoretic behavior is a result of question-answer dynamics, which are pervasive in human reasoning (Koralus & Mascarenhas 2013, 2018; Sabl ́e-Meyer & Mascarenhas 2021). Again returning to the lawyers-engineers example, I argue that participants consider the description they are given as a hint at an answer, as if uttered by a cooperative and well-informed speaker, meant to help them determine which of the two alternatives is most likely to be true. In this framing of the task, confirmation-theoretic behavior is the result of relevance-based reasoning, as has been formalized in various ways within the literature on linguistic pragmatics. I give a unified account of multiple data points from the heuristics and biases literature and from deductive reasoning in terms of question-answer dynamics, recruiting theories of questions from linguistic semantics and philosophical logic. Additionally, I report on a behavioral experiment that recreates question-answer dynamics with minimal language use, showing that these phenomena do not wholly depend on language.

Freitag, 20. Mai 2022 um 13:30 – 15:00 Uhr, Oberseminar Relle Geometrie und Algebra

Lucas Slot (CWI Amsterdam)

(Gast von Markus Schweighofer)

Convergence analysis of sum-of-squares hierarchies for polynomial optimization

Consider the problem of minimizing a polynomial f over a compact, semialgebraic set X. In this talk, we look at several hierarchies of approximations for this hard, non-convex optimization problem based on sums of squares. On the one hand, we have the well-known moment-SOS hierarchy, due to Lasserre and Parrilo, which provides *lower* bounds on the minimum of f. On the other hand, we have Lasserre's measure-based hierarchies, which provide *upper* bounds. Our goal is to prove theoretical guarantees on the quality of these approximations as the level of the hierarchy increases.
For the lower bounds, we prove strong guarantees for special sets X with symmetric structure, which include the (binary) hypercube, the unit ball and the standard simplex. These results rely on the theory of Fourier analysis, reproducing kernels and (extremal roots of) orthogonal polynomials.
For the upper bounds, we show how to extend a known best-possible guarantee on the hypercube [-1, 1]^n to a (much) broader class of convex bodies X. Furthermore, we obtain a guarantee which is nearly as good for all compact, semialgebraic sets X with dense interior. We again rely on a link to orthogonal polynomials, as well as known polynomial approximations for Dirac measures on the interval.

Montag, 23.Mai 2021 um 15:15 Uhr, Oberseminar Complexity Theory, Model Theory, Set Theory.

Lorenzo Venturello (KTH Stockholm)

(Gast von Mateusz Michalek and Salma Kuhlmann)

Gorenstein algebras form an intriguing class of objects which often show up in combinatorics and geometry. In this talk I will present a construction which associates to every pure simplicial complex a standard graded Gorenstein algebra. We describe a presentation of this algebra as a polynomial ring modulo an ideal generated by monomials and pure binomials. When the simplicial complex is flag, i.e., it is the clique complex of its graph, our main results establish equivalences between well studied properties of the complex (being S_2, Cohen-Macaulay, Shellable) with those of the algebra (being quadratic, Koszul, having a quadratic GB). Finally, we study the h-vector of the Gorenstein algebras in our construction and answer a question of Peeva and Stillman by showing that it is very often not gamma-positive. This is joint work with Alessio D'Alì.

Montag, 30.Mai 2021 um 15:15 Uhr, Logic Colloquium

Inger Bakken Pedersen(University of Vienna)

(Gast von Salma Kuhlmann and Carolin Antos-Kuby)

Coherentist Structuralism

I pursue a position I will call coherentist structuralism. It is a combination
view that unites: i) a position’s ontological commitments, and ii) metaontological considerations. The metaontological component consists of coherentist minimal-ism, while the ontological commitments are those of non-eliminative structuralism. The aim is to show that these are compatible with each other, and will reciprocally inform and clarify the other position. I argue that the structuralist benefits from a combination view with metaontological ambitions. The central claim of structuralism – that abstract structures exist – is given added justification, as the metaontological framework qualifies the ontological commitments made. To this end, I look to coherence theories in analytic epistemology, as the notion of ‘coherence’ is unclear. The upshot is that coherentist structuralism better accounts for when we allow structures to exist, as it offers a framework in which existence claims can be expressed in terms of coherence.

Freitag, 3. Jun 2022 um 13:30 – 15:00 Uhr, Oberseminar Relle Geometrie und Algebra

Daniel Plaumann(TU Dortmund)

(Gast von Claus Scheiderer)

Families of faces for convex semi-algebraic sets

Given a convex semi-algebraic set, presented for example as the convex hull of an algebraic variety, by a matrix inequality or in some other way, we seek to subdivide its boundary into well-behaved families of faces. To this end, we give a semi-algebraic definition of a "patch", a notion introduced by Ciripoi, Kaihnsa, Löhne, and Sturmfels. The talk will focus on examples and highlight some key results. (Joint work with Rainer Sinn and Jannik Wesner)

Freitag, 10. Jun 2022 um 13:30 – 15:00 Uhr, Oberseminar Relle Geometrie und Algebra

Lorenzo Baldi (Inria Sophia Antipolis-Méditerranée)

(Gast von Claus Scheiderer)

Convergence Rates and Flat Truncation for in Lasserre's Hierarchies

After briefly recalling the construction of Lasserre's Moment and Sum of Square hierarchies, we present a new, general, polynomial version of Putinar's Positivstellensatz. This result implies that Lasserre's hierarchies have polynomial convergence. Then we investigate finite convergence of the hierarchies,
and in particular the flat truncation property, with its connections to zero dimensional ideals. We present a new, necessary and sufficient condition for flat truncation, and finally discuss a related open question in the positive dimensional case. Based on joint works with Bernard Mourrain and Adam Parusinski.

Montag, 13.Jun 2021 um 15:15 Uhr, Oberseminar Complexity Theory, Model Theory, Set Theory.

Yairon Cid-Ruiz(KU Leuven)

(Gast von Mateusz Michalek and Salma Kuhlmann)

The fiber-full scheme

We introduce the fiber-full scheme which can be seen as the parameter space that generalizes the Hilbert and Quot schemes by controlling the entire cohomological data. In other words, the fiber-full scheme controls the dimension of all cohomologies of all possible twistings, instead of just the Hilbert polynomial. We also present some applications that can be derived from the existence of the fiber-full scheme. This talk is based on joint work with Ritvik Ramkumar.

Freitag, 15.Juli 2022 um 13:30 – 15:00 Uhr, Oberseminar Relle Geometrie und Algebra

Vincenzo Galgano (Uniniversity of Trento)

(Gast von Mateusz Michalek)

Equivariant Euler characteristics on permutohedral varieties

Permutohedral varieties are geometric-combinatorial objects arising both from classical algebraic geometry and from toric geometry: they can be defined as the blowup of a projective space at the Cremona-map singularities, or as the toric variety whose lattice polytope is a permutohedron. In this talk we present the combinatorics of some torus-invariant divisors on a permutohedral variety and determine the equivariant Euler characteristic of certain vector bundles they define. Based on a current joint work with Mateusz Michalek and Hanieh Keneshlou.

Montag, 18.Juli 2021 um 15:15 Uhr, Oberseminar Complexity Theory, Model Theory, Set Theory.

Nicolas Daans(University of Antwerp)

(Gast von Markus Schweighofer)

How many quantifiers are needed to existentially define a subset of a field?

When a subset of a field is existentially definable, one can ask what the smallest number of quantifiers is needed for an existential formula defining this set. This question turns out to be quite hard in general, since answering it requires a thorough understanding of the arithmetic of the field in question. On the other hand, if one asks how many quantifiers are needed to existentially define a definable class of subsets (e.g. the set of sums of 4 squares) uniformly across fields, then the problem gets a much more geometric flavour, can be tackled via a model-theoretic approach, and is connected with the notions of essential and canonical dimension, as introduced by Merkurjev. We discuss some techniques, results, and open questions. Based on joint work with Arno Fehm and Philip Dittmann.