This is the website for the Conference Geometry in Complexity and Computations, september 21.-23., 2022, at the University of Konstanz.
All talks will take place in room K0503 on the main campus. The conference is partly funded by Foundation Compositio Mathematica. The event will also celebrate Peter Bürgisser and his contributions to the field on the occasion of his 60th birthday. |
09:00 - 10:15 | 10:45 - 12:00 | 14:00 - 15:15 | 15:45 - 17:00 |
---|---|---|---|
Christian Ikenmeyer | Greta Panova | Michael Walter | Kathlén Kohn |
University of Liverpool | University of Southern California | Ruhr University Bochum | KTH Stockholm |
Title: Geometric Complexity Theory | Title: Complexity and Algebraic Combinatorics | Title: Symmetries of Computational Problems and Optimization | Title: Invariant theory of maximum likelihood estimation |
I will give a short introduction to geometric complexity theory, an approach towards the separation of algebraic complexity classes using algebraic geometry and representation theory, and I will report on several results in the area that appeared since the 2014 Simons Institute program on Algorithms and Complexity in Algebraic Geometry. | The complexity of computing polynomials can be understood via their algebraic and geometric properties and symmetries. Geometric Complexity Theory (GCT) translates these problems to Representation Theory, whereby inequalities between multiplicities of irreducible representations could give computational lower bounds. Such multiplicities are also a subject of study of Algebraic Combinatorics, where the classical but mysterious Kronecker and plethysm coefficients pose some of the main open problems. In this talk we will define the main objects and discuss these connections. | Many computational problems are invariant under hidden symmetries. Revealing them can be an essential tool to obtaining new structural insight and finding fast algorithms. In this lecture I will give an introduction to these connections, which are rooted in invariant theory, survey some applications from statistics to quantum information, and sketch how optimization in curved spaces (which arise naturally from non-commutative symmetries) has recently led to significant progress. | The task of fitting data to a model is fundamental in statistics. A widespread approach is finding a maximum likelihood estimate (MLE), where one maximizes the likelihood of observing the data as we range over the model. For two common statistical settings (log-linear models and Gaussian transformation families), we show that that approach is equivalent to a capacity problem in invariant theory: finding a point of minimal norm in an orbit under a corresponding group action. The latter problem has been recently studied in a series of papers co-authored by Peter Bürgisser. We show that the existence of the MLE can be characterized by stability notions under the group action. Moreover, algorithms from statistics can be used in invariant theory, and vice versa. This talk provides an introduction to this dictionary between invariant theory and statistics, which has already led to the solution of long-standing questions concerning the MLE of matrix normal models. This talk is based on joint work with Carlos Améndola, Philipp Reichenbach, and Anna Seigal. |
09:00 - 10:15 | 10:45 - 12:00 | 13:30 - 14:45 | 15:15 - 16:30 |
---|---|---|---|
Martin Lotz | Ada Boralevi | Carlos Beltrán | Sandra di Rocco |
Warwick University | Politecnico de Torino | Universidad de Cantabria | KTH Stockholm |
Title: Geometric Probability in Optimization and Complexity | Title: Uniform determinantal representations and spaces of singular matrices | Title: When can forward stable algorithms be composed stably | Title: Geometry of Algebraic Data |
Geometric probability and integral geometry have played a role in the probabilistic analysis of algorithms in optimization at least since the work of Smale, Renegar, Vershik, and others in the 1980s. We give an overview of the interaction between geometric probability, computational complexity and optimization, with an emphasis on Peter Buergisser's contributions to the field. We will then outline how ideas originating from the complexity of optimization methods led to new developments in fields ranging from compressed sensing to combinatorics and discuss some new developments and open problems. | The problem of expressing a specific polynomial as the determinant of a square matrix of affine-linear forms arises from algebraic geometry, optimization, complexity theory, and many more areas. In this talk I will introduce the notion of "uniform determinantal representation", and derive a lower bound on the size of the matrix, showing a construction achieving that lower bound up to a constant factor as the number of variables is fixed and the degree grows. I will also relate uniform determinantal representations to vector spaces of singular matrices, in particular compression spaces. The paper I will report on is a joint work with van Doornmalen, Draisma, Hochstenbach, and Plestenjak. | Although stability has been widely studied in the mathematical literature, there are very simple questions such as that of the title, which still need an answer. Working on the concept of condition number, we state some widely satisfied hypotheses, depending only on two functions g and h, under which the composition of a stable algorithm for g and a stable algorithm for h is a stable algorithm for the composition g∘h. | It is often convenient to visualize algebraic varieties (and hence systems of polynomial equations) by sampling. The key challenge is to have the right distribution and density in order to recover the shape, i.e the topology of the variety. Bottlenecks are pairs of points on the variety joined by a line which is normal to the variety at both points. These points play a special role in determining the appropriate density of a point-sample. Under suitable genericity assumptions the number of bottlenecks of an affine variety is finite and is called the bottleneck degree. Estimations of the bottleneck degree and certain generalizations lead to efficient sampling techniques. We will show how classical projective algebraic geometry has proven very useful in this analysis. The talk is based on joint work with D. Eklund, P. Edwards, O. Gäfvert, J Hauenstein, M. Weinstein. |
09:00 - 10:15 | 10:45 - 12:00 | 13:30 - 14:45 | 15:15 - 16:30 |
---|---|---|---|
Marie-Francoise Roy | Alicia Dickenstein | Matthias Christandl | Avi Wigderson |
IRMAR | Universidad de Buenos Aires | University of Copenhagen | IAS Princeton |
Title: Divide and conquer roadmap algorithm for basic semi-algebraic sets | Title: Beyond Boolean Networks | Title: Quantum Information and Algebraic Complexity | Title: Permanent & Determinant: non-identical twins |
In this new step of our long term project on the complexity of roadmaps, we were hoping to be able to use directly our previous work on Divide and conquer roadmaps for algebraic sets. Of course, a significant part of it can be adapted but several new ideas and techniques are needed. The talk will start with an overview of existing complexity results for roadmaps and describe our results in progress. Based on a joint work with Saugata Basu. | I will report on work in progress with Juliana García Galofre, Mercedes Pérez Millán and Reinhard Laubenbacher, which is an invitation to model biological networks with any finite number m of states for every node; in particular, to predict the qualitative behavior of gene regulatory networks. To model the dynamics, we represent each transition function via operations used in multivalued logic, which are intuitive and close to biological interpretations. We generalize several properties of Boolean networks (the case m=2) and we give an algorithm to compute the fixed points of the system, including some complexity considerations. | Quantum Information and Algebraic Complexity are unexpected partners in their use of tensors, asymptotics and representation theory. I will highlight the philosophy, present key results and give an update (maybe including live quantum computing in the cloud), so that we can appreciate the relation that Bohr-Einstein have to Strassen-Bürgisser. | The Determinant is undoubtedly the most important polynomial function in mathematics. Its lesser known sibling, the Permanent, plays very important roles in enumerative combinatorics, statistical and quantum physics, and the theory of computation. In this lecture I plan to survey some of the many remarkable properties of the permanent, its applications and impact on fundamental computational problems, its similarities to and apparent differences from the determinant, and how these relate to the P vs. NP prolem. This lecture is intended to a general Math & CS audience. |