Webinar

From SIAG-AG

SAGA - Seminar on Applied Geometry and Algebra

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.

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).

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.

• Tuesday, November 9, 5pm Central European Time (UTC+1):
  Jonathan Hauenstein (University of Notre Dame) Time Zones

• Tuesday, December 7 (Special week! The first Friday of the month), 5pm Central European Time (UTC+1):
  Alicia Dickenstein (University of Buenos Aires) Time Zones

• Tuesday, January 11, 5pm Central European Time (UTC+1):
  TBD (TBA) Time Zones

• Tuesday, February 8, 5pm Central European Time (UTC+1):
  TBD (TBA) Time Zones

• Tuesday, March 8, 5pm Central European Time (UTC+1):
  TBD (TBA) Time Zones

• Tuesday, April 12, 5pm Central European Summer Time (UTC+2):
  TBD (TBA) Time Zones

• Tuesday, May 10, 5pm Central European Summer Time (UTC+2):
  TBD (TBA) Time Zones

• Tuesday, June 13, 5pm Central European Summer Time (UTC+2):
  TBD (TBA) Time Zones

Format The seminars are held on Zoom:

• 45 minutes of presentation, incl. questions
• informal discussion
• Fill out the SAGA registration to get a personalized Zoom link for each seminar.

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.

Each Zoom meeting is provided by SIAM. The webinars will be recorded and posted in the SAGA playlist on SIAM’s YouTube account.

Organizers

• Kathlén Kohn (KTH Stockholm)
• Jose Israel Rodriguez (University of Wisconsin - Madison)
• Joachim Rosenthal (University of Zurich)

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.