Webinar
From SIAG-AG
(Difference between revisions)
| Revision as of 12:27, 24 March 2022 (edit) JoRo7102 (Talk | contribs) (→Upcoming Talks) ← Previous diff |
Revision as of 17:47, 25 March 2022 (edit) (undo) JoRo7102 (Talk | contribs) (→April 2022) Next diff → |
||
| Line 47: | Line 47: | ||
| === April 2022=== | === April 2022=== | ||
| - | * Tuesday, April 12, 5pm Central European Summer Time (UTC+2): <br> '''Jesús A. De Loera''' (U.C. Davis) [https://www.timeanddate.com/worldclock/converter.html?iso=20220412T150000&p1=3736&p2=25&p3=270&p4=3999 Time Zones]<br> '''The geometry of the space of ALL pivot rules of a Linear Optimization problem''' | + | * Tuesday, April 12, 5pm Central European Summer Time (UTC+2): <br> '''Jesús A. De Loera''' (U.C. Davis) [https://www.timeanddate.com/worldclock/converter.html?iso=20220412T150000&p1=3736&p2=25&p3=270&p4=3999 Time Zones]<br> ''The geometry of the space of ALL pivot rules of a Linear Optimization problem'' <br> Linear optimization is a simple yet fundamental building block in modern computing (e.g., without linear programs and branch-and-cut methods one would not have solvers for integer optimization). Dantzig's Simplex Method is one of the most popular algorithms for linear optimization. It was even named as one of the top ten algorithms in the 20th century. But despite all its success and popularity for the last 80 years we still do not fully understand it. There are still a number of open questions about its behavior and this talk is about how to choose a pivot rule? <br> Purely geometrically, a linear program (LP) is a polyhedron together with an orientation of its graph. A simplex method selects a directed path from an initial vertex to the sink (optimum) and thus determines an arborescence (of shortest monotone paths). The engine of any simplex method is a pivot rule that selects the outgoing arc for a current vertex. Pivot rules come in many forms and types but we are still ignorant whether there is one that can make the simplex method run in polynomial time. Somehow we need ways to grasp the set of all possible pivot rules. In this talk we show this set has a very natural polyhedral structure. <br> Classic results in parametric linear optimization explain the changes of objective function, e.g., the orientation and sink and for a pivot rule its associated arborescence. I present a new parametric analysis for all pivot rules belonging to a certain class, memoryless pivot rules. It turns out there exist lovely polytopes, the pivot rule polytopes, that parametrize all memoryless pivot rules of a given LP. This is an attempt to get a geometric/topological picture of the “ space of all pivot rules of an LP”. <br> I will present this entertaining story without assuming prior knowledge of linear programming or the simplex method. The story is related to performance of pivot rules, fiber polytopes, parametric linear programs, shadow-vertex-rules, and several classic polytopes make cameo appearances. This is joint work with Alex Black (UC Davis), Niklas Lu ̈tjeharms (U. Frankfurt), and Raman Sanyal (U. Frankfurt). |
| === May 2022=== | === May 2022=== | ||
Revision as of 17:47, 25 March 2022
Contents |
SAGA - Seminar on Applied Geometry and Algebra
About. Over the last years there has been an immense growth of nonlinear models across the mathematical sciences and its applications to other disciplines. This is fueled by recent theoretical advances in understanding systems of multivariate polynomial equations and inequalities, development of efficient software solving such systems, and an increased awareness of these tools. SIAM SAGA features talks on algebraic geometry and its links to other mathematical branches -- such as combinatorics, algebraic topology, commutative algebra, convex and discrete geometry, tensors and multilinear algebra, number theory, representation theory, and symbolic and numerical computation --, focusing on a variety of applications -- including robotics, optimization, statistics, machine learning, complexity theory, cryptography, coding theory, computer vision, biology, economics, among many others.
Registration. Fill out the SAGA registration form (takes 10 seconds) to get a personalized Zoom link for each seminar.
Recordings. The webinars are recorded and posted in the SAGA playlist on SIAM’s YouTube account.
Mailing List. To stay up-to-date about upcoming talks and receive Zoom invitations please join our mailing list by sending an email to siam_saga+join@g-groups.wisc.edu.
- Afterwards you will receive an email which asks you to confirm your wish for subscription by replying to that email.
- Finally, you will receive a confirmation email that you became a member.
- If you have questions about the mailing list, then email jRodriguez43@wisc.edu (Jose Rodriguez).
Format. The seminars are held on a Zoom Webinar provided by SIAM:
- 45 minutes of presentation, incl. questions
- informal discussion
- Participants can ask questions in the Q&A. The chair will bring forward these questions during and after the talk, and may ask you to unmute yourself to participate in the discussion. Please note that you will be recorded if you activate your audio or video during the seminar.
Organizers.
- Kathlén Kohn (KTH Stockholm)
- Jose Israel Rodriguez (University of Wisconsin - Madison)
- Joachim Rosenthal (University of Zurich)
Upcoming Talks
All seminars take place on the 2nd Tuesday of every month.
Fill out the SAGA registration to get a personalized Zoom link for each seminar.
February 2022
- Tuesday, February 8, 5pm Central European Time (UTC+1):
Heather Harrington (Oxford) Time Zones - Algebra and topology for biological systems
- Abstract: Signalling pathways in molecular biology can be modeled by polynomial dynamical systems. I will present mathematical models describing two biological systems involved in development and cancer. I will overview approaches to analyse these models with data using computational algebraic geometry, differential algebra and statistics. I will also present how topological data analysis can provide additional information to distinguish wild-type and mutant molecules in one pathway. These case studies showcase how computational algebra, geometry, topology and dynamics can provide new insights to better understand model parameter values as well as biological systems with time course data, specifically how changes at the molecular scale (e.g. molecular mutations) result in kinetic differences that are observed as phenotypic changes (e.g. mutations in fruit fly wings).
March 2022
- Tuesday, March 8, 5pm Central European Time (UTC+1):
Dustin Mixon (THE Ohio State) Time Zones - Packing points in projective spaces
- Abstract: Given a compact metric space, it is natural to ask how to arrange a given number of points so that the minimum distance is maximized. For example, the setting of the 2-sphere prompted a dispute between Newton and Gregory in 1694, and the setting of Hamming space forms the foundation of error correction in modern digital communication. In this talk, we consider the setting of real and complex projective spaces. We briefly discuss applications before surveying the state of the art and identifying key open problems.
April 2022
- Tuesday, April 12, 5pm Central European Summer Time (UTC+2):
Jesús A. De Loera (U.C. Davis) Time Zones
The geometry of the space of ALL pivot rules of a Linear Optimization problem
Linear optimization is a simple yet fundamental building block in modern computing (e.g., without linear programs and branch-and-cut methods one would not have solvers for integer optimization). Dantzig's Simplex Method is one of the most popular algorithms for linear optimization. It was even named as one of the top ten algorithms in the 20th century. But despite all its success and popularity for the last 80 years we still do not fully understand it. There are still a number of open questions about its behavior and this talk is about how to choose a pivot rule?
Purely geometrically, a linear program (LP) is a polyhedron together with an orientation of its graph. A simplex method selects a directed path from an initial vertex to the sink (optimum) and thus determines an arborescence (of shortest monotone paths). The engine of any simplex method is a pivot rule that selects the outgoing arc for a current vertex. Pivot rules come in many forms and types but we are still ignorant whether there is one that can make the simplex method run in polynomial time. Somehow we need ways to grasp the set of all possible pivot rules. In this talk we show this set has a very natural polyhedral structure.
Classic results in parametric linear optimization explain the changes of objective function, e.g., the orientation and sink and for a pivot rule its associated arborescence. I present a new parametric analysis for all pivot rules belonging to a certain class, memoryless pivot rules. It turns out there exist lovely polytopes, the pivot rule polytopes, that parametrize all memoryless pivot rules of a given LP. This is an attempt to get a geometric/topological picture of the “ space of all pivot rules of an LP”.
I will present this entertaining story without assuming prior knowledge of linear programming or the simplex method. The story is related to performance of pivot rules, fiber polytopes, parametric linear programs, shadow-vertex-rules, and several classic polytopes make cameo appearances. This is joint work with Alex Black (UC Davis), Niklas Lu ̈tjeharms (U. Frankfurt), and Raman Sanyal (U. Frankfurt).
May 2022
- Tuesday, May 10, 5pm Central European Summer Time (UTC+2):
Gretchen Matthews (Virginia Tech) Time Zones
June 2022
- Tuesday, June 14, 5pm Central European Summer Time (UTC+2):
TBD (TBA) Time Zones
Past Talks
These seminars already happened. But you can fill out the SAGA registration to get a personalized Zoom link for future seminars.
- Tuesday, November 10, 5pm Central European Time (UTC+1): Time zones
Rekha R. Thomas (University of Washington)
When Two Cameras Meet a Cubic Surface
The set of images captured by an arrangement of pinhole cameras is usually modeled by the multiview variety. The true set is in fact a semialgebraic subset of this variety, arising from the physical restriction that cameras can only image points in front of them. For a pair of cameras, the minimal problem in this semialgebraic setting is given by 5 point pairs, which even in general position, can fail to have a "chiral" reconstruction. I will describe how the combinatorics and arithmetic information of this minimal case is carried by a cubic surface with 27 real lines.
Joint work with Sameer Agarwal, Andrew Pryhuber and Rainer Sinn.
- Tuesday, December 8, 5pm (Central European Time) (UTC+1): Other time zones
Camilla Hollanti (Aalto University)
Coding theoretic framework for private information retrieval
Private information retrieval (PIR) addresses the question of how to retrieve data items from a database or cloud without disclosing information about the identity of the data items retrieved. The area has received renewed attention in the context of PIR from coded storage systems. Here, the files are distributed over the servers according to a storage code instead of mere replication of data. Alongside with the basic principles of linear codes and PIR, we will review recent PIR capacity results and retrieval schemes. Then, we will introduce our own general framework allowing one to adjust the scheme according to the desired storage overhead and suspected collections of colluding servers. This is achieved by a carefully designed interplay between the algebraic-geometric storage and retrieval codes, coined as the star product scheme. The talk is based on a collection of joint works with Salim El Rouayheb (Rutgers), Ragnar Freij-Hollanti (Aalto), Oliver Gnilke (Aalborg), Lukas Holzbaur (TU Munich), David Karpuk (F-Secure), Jie Li (Aalto), and Razan Tajeddine (Helsinki).
- Tuesday, January 12, 5pm Central European Time (UTC+1): Other time zones
Sonja Petrović (Illinois Institute of Technology)
Random Monomial Ideals
Joint work with Jesus A. De Loera, Lily Silverstein, Despina Stasi, Dane Wilburne.
Inspired by the study of random graphs and simplicial complexes, and motivated by the need to understand average behavior of ideals, we propose and study probabilistic models of random monomial ideals. We prove theorems about the probability distributions, expectations and thresholds for events involving monomial ideals with given Hilbert function, Krull dimension, first graded Betti numbers, and present several experimentally-backed conjectures about regularity, projective dimension, strong genericity, and Cohen-Macaulayness of random monomial ideals.
The models for monomial ideals can be used as a basis for generating other types of algebraic objects, and proving existence of desired properties. The talk will feature a tasting of ongoing work in both of these directions.
- Tuesday, February 9, 5pm Central European Time (UTC+1): Other time zones
Bernd Sturmfels (MPI MiS Leipzig, UC Berkeley)
Linear Spaces of Symmetric Matrices
Real symmetric matrices appear ubiquitously across the mathematical sciences, and so do linear spaces of such matrices. We discuss recent developments concerning their algebraic geometry, with a view towards applications in statistics and optimization.
- Tuesday, March 9, 5pm Central European Time (UTC+1):
Timo de Wolff (Technische Universität Braunschweig)
Certificates of Nonnegativity and Their Applications in Theoretical Computer Science
Certifying nonnegativity of real, multivariate polynomials is a key problem in real algebraic geometry since the 19th century. In the 21st century, the problem (re-)gained significant momentum due to its relevance in polynomial optimization and its applications. The classical standard certificates of nonnegativity are sums of squares (SOS). But other, independent certificates of nonnegativity exist: e.g., sums of nonnegative circuit polynomials (SONC), which I have developed joint with Iliman in 2014.
In the first part of this talk, I give an overview about certificates and hierarchies of nonnegativity. In the second part, I discuss highlights of recent work joint with Dressler and Kurpisz about theoretical bounds for hierarchies (of nonnegativity) applied to polynomial optimization problems on the Boolean Hypercube. This class includes in particular standard problems in theoretical computer science such as Maxcut or Knapsack, which motivated our work.
- Tuesday, April 13, 5pm Central European Summer Time (UTC+2):
Jan Draisma (Universität Bern)
Infinite-dimensional geometry with symmetry
Most theorems in finite-dimensional algebraic geometry break down in infinite dimensions---for instance, the polynomial ring C[x_1,x_2,...] is not Noetherian. However, it turns out that some results do survive when a sufficiently large symmetry group is imposed; e.g., ideals in C[x_1,x_2,...] that are preserved under all variable permutations do satisfy the ascending chain condition.
This phenomenon is relevant for applications, since many algebraic models come in infinite families with highly symmetric infinite-dimensional limits. Here the symmetry is typically captured by either the infinite symmetric group or the infinite general linear group. Theorems about the limit imply uniform behaviour of the members of the family.
I will present older and new results in this area, along with applications to algebraic statistics, tensor decomposition, and algebraic combinatorics.
- Tuesday, May 11, 5pm Central European Summer Time (UTC+2):
Elisenda Feliu (University of Copenhagen)
Parametric polynomial systems and biochemical reaction networks
In the context of (bio)chemical reaction networks, the dynamics of the concentrations of the chemical species over time are often modelled by a system of parameter-dependent ordinary differential equations, which are typically polynomial or described by rational functions. The study of the steady states of the system translates then into the study of the positive solutions to a parametric polynomial system.
In this talk I will start by shortly presenting the formalism of the theory of reaction networks. Afterwards I will focus on the study of the parameter region where the relevant parametric system admits at least two positive solutions (a property termed multistationarity). I will show recent results on how to determine the region and whether it is connected. A ubiquitous and challenging network from cell signaling (the dual futile cycle) will be used as a case example. For this network, which is relatively small, several basic questions remain unresolved.
The results I present arise from several joint works involving Conradi, Kaihnsa, Mincheva, Sadeghimanesh, Telek, Yürük, Wiuf and de Wolff.
- Tuesday, July 13, 5pm Central European Summer Time (UTC+2): Time zones
Caroline Uhler (MIT, Broad Institute)
Mathematics of Genome Packing and Regulation
Recent evidence suggests that the spatial organization of the genome represents an important regulator of expression, and alterations thereof are associated with various diseases. In this talk, I will analyze the link between the 3D genome organization and gene expression using geometric packing models and autoencoders/deep learning. In particular, I will first discuss the Euclidean distance geometry problem arising when studying the 3D genome organization and show that higher-order contacts are needed for its reconstruction. I will then discuss how autoencoders can be used to translate between DNA packing images and gene expression at the single-cell level as well as between different cell types. Given the empirical benefits of over-parameterization in autoencoders for these applications, I will end with a theoretical analysis of autoencoders linking over-parameterization to attractor properties. Understanding the geometry of these basins of attraction remains an important open problem.
- Tuesday, August 10, 5pm Central European Summer Time (UTC+2): Time zones
Frank Sottile (Texas A&M)
Applications of Bernstein's Other Theorem
Many of us are familiar with Bernstein's Theorem giving the number of solutions in the torus to a general system of sparse polynomial equations. The linchpin of his proof is what I like to call Bernstein's Other Theorem, which describes exactly when a system fails to be general in the above sense (Bernstein-general). His bound is a simple consequence of this using, for example, the characterization of mixed volume.
Polynomial systems in nature are rarely general given their supports, and thus Bernstein's Theorem is only a priori a bound for their number of solutions. Nevertheless, a surprising number of polynomial systems from applications do achieve Bernstein's bound. For such a system, the polyhedral homotopy give an optimal algorithm for computing its solutions. My talk will discuss this background and give some polynomial systems from applications which are not general given their support, but are Bernstein-general.
- Tuesday, September 14, 5pm Central European Summer Time (UTC+2): Time zones
Elisa Gorla (University of Neuchatel)
Multivariate cryptography and the complexity of polynomial system solving
The security of multivariate cryptographic primitives relies on the hardness of computing the solutions of multivariate polynomial systems over finite fields. Since we can compute the solutions of a polynomial system from its Groebner basis, bounds on the complexity of Groebner bases computations provide bounds on the security of the corresponding multivariate cryptographic primitives. After introducing multivariate cryptography, I will discuss linear-algebra-based methods for computing Groebner bases, which are currently considered the most efficient algorithms available. I will introduce some invariants which control this complexity and try to answer the question of how hard it is to solve a "random" polynomial system.
- Tuesday, October 12, 5pm Central European Summer Time (UTC+2): Time zones
Avi Wigderson (Institute for Advanced Study)
Optimization, Complexity and Math (or, can we prove P!=NP by gradient descent?)
This talk aims to summarize a project I was involved in during the past 6 years, with the hope of explaining our most complete understanding so far, as well as challenges and open problems. The main messages of this project are summarized below; I plan to describe, through examples, many of the concepts they refer to, and the evolution of ideas leading to them. No special background is assumed.
(1) The most basic tools of convex optimization in Euclidean space extend to a far more general setting of Riemannian manifolds that arise from the symmetries of non-commutative groups. We develop first-order and second-order algorithms, and analyze their performance in general. While proving convergence bounds requires heavy algebraic and analytic tools, convergence itself depends in an elegant way on natural ``smoothness’’ parameters, in analogy with the Euclidean (commutative) case.
(2) These algorithms give exponential (or better) improvements in run-time for solving algorithmic many problems across CS, Math and Physics. In particular, these include problems in algebra (e.g. testing rational identities in non-commutative variables), in analysis (testing the feasibility and tightness of Brascamp-Lieb inequalities), in quantum information theory (to the quantum marginals problem), in algebraic geometry (to computing Kronecker coefficients), in computational complexity (to derandomizing new special cases of the PoIynomial Identity Testing problem) and in optimization (to testing membership in large, implicitly described polytopes).
(3) The focus on symmetries exposes old and reveals new relations between the problems above, and between analysis, algebra and algorithms. Essentially, they are all membership problems in null cones and moment polytopes of natural group actions on natural spaces. Invariant theory, which studies such group actions, plays an essential role in this development. In particular, a beautiful non-commutative duality theory (expending linear programming duality in the commutative case), and notions of geodesic convexity (extending the Euclidean one) and moment maps (extending the Euclidean gradient) are central to the algorithms and their analysis. Interestingly, most algorithms in invariant theory are symbolic/algebraic, and these new numeric/analytic algorithms proposed here often significantly improve on them.
Based on joint works with Zeyuan Allen-Zhu, Peter Burgisser, Cole Franks, Ankit Garg, Leonid Gurvits, Pavel Hrubes, Yuanzhi Li, Visu Makam, Rafael Oliveira and Michael Walter.
- Tuesday, November 16, (Special week! Third Tuesday of the month!) 5pm Central European Time (UTC+1):
Jonathan Hauenstein (University of Notre Dame) Time Zones
Some applications of homotopy continuation in science and engineering
Homotopy continuation is a foundational computational approach in numerical algebraic geometry which permits the tracking of solutions to parameterized systems of nonlinear equations. In science and engineering applications, parameters such as temperature, pressure, and leg lengths naturally arise and changing such parameters can impact both the qualitative and quantitative behavior of the corresponding solutions. This talk will provide an overview of homotopy continuation followed by several applications of homotopy continuation including equilibria in chemistry, kinematic synthesis in mechanical engineering, and variational inference for parameter estimation in biological models.
- Tuesday, December 7 (Special week! The first Tuesday of the month), 5pm Central European Time (UTC+1):
Alicia Dickenstein (University of Buenos Aires) Time Zones
Families of polynomials in the study of biochemical reaction networks
The standard mass-action kinetics modeling of the dynamics of biochemical reaction networks gives rise to systems of ordinary polynomial differential equations with (in general unknown) parameters. Attempts to explore the parameter space in order to predict properties of the associated systems challenge the standard current computational tools because even for moderately small networks we need to study families of polynomials with many variables and many parameters. These polynomials have a combinatorial structure that comes from the digraph of reactions. We show that different techniques can be strengthened and applied for biochemical networks with special structure.
- Tuesday, January 11, 5pm Central European Time (UTC+1):
Cynthia Vinzant (University of Washington)
Symmetry and determinantal polynomials
Symmetry appears in many ways in the study of matrix spaces and determinantal representations. A multivariate polynomial is called determinantal if it can be written as the determinant of a square matrix of linear forms. The study of determinantal representations stretches from 19th century algebraic geometry to modern day applications in matrix theory and the geometry of polynomials. Individual symmetric polynomials have representations certifying their symmetry and the set of determinantal polynomials is invariant under a large group action. In this talk, I will introduce this theory and talk about both instances of symmetry in the study of determinantal polynomials. Specifically, I will discuss representations of plane curves invariant under the action of the cyclic and dihedral groups as well as a connection between determinantal representations of multiaffine polynomials and the principal minor map. This is based on joint works with Abeer Al Ahmadieh, Daniel Plaumann, and Faye Pasley Simon.
