Summer School on Randomness and Learning in Non-Linear Algebra

Abstracts for the talks

Peter Buergisser
Technische Universität Berlin
Finding the homology of semialgebraic sets, certified by condition numbers
We begin by explaining an algorithm due to Niyogi, Smale and Weinberger for finding the homology of manifolds, in which the reach turns out to be the critical complexity parameter. We then go on to explain how the reach of a semialgebraic set can be bounded in terms of a condition number. Finally, we outline a numerically stable algorithm to compute the homology of basic semialgebraic sets that runs in single exponential time, outside a vanishingly small set of ill-conditioned input data.
The talk is mainly based on the joint paper with Felipe Cucker and Pierre Lairez (J ACM 2018).

Daniel Erman
University of Wisconsin-Madison
Randomness and syzygies
I will discuss how probabilistic constructions, especially those stemming from random flag complexes, can shed light on conjectures about syzygies.

Serkan Hosten
San Francisco State University
Average Behavior of Monomial Free Resolutions
We present our result that under a natural probability distribution for generating minimal generators, a monomial ideal in n indeterminates almost always has a minimal free resolution of length n. We will also touch upon the Scarf complexes of "average" monomial ideals and the Betti numbers of such ideals.

David Kahle
Baylor University
Stochastic Exploration of Real Varieties and Applications
Nonlinear systems of polynomial equations arise naturally in many applied settings. The solution sets to these systems over the reals are often positive dimensional spaces that in general may be very complicated yet have very nice local behavior almost everywhere. Standard methods in real algebraic geometry for describing positive dimensional real solution sets include cylindrical algebraic decomposition and numerical cell decomposition, both of which can be costly to compute in many practical applications. In this talk, we communicate recent progress towards a Monte Carlo framework for exploring such real solution sets. After describing how to construct probability distributions whose mass focuses on a variety of interest, we use Hamiltonian Monte Carlo to sample points near the variety that may then be magnetized to the variety using endgames. We conclude by showcasing trial experiments and applications using implementations in R and Stan.

This work is joint with Jonathan Hauenstein.

Robert Krone
University of California, Davis
Predictions and learning with random monomial ideals
Many computational problems on polynomial ideals are known to have bad worst-case running times. Can we instead make a quick probabilistic guess at the answer? One strategy is to understand what properties are very likely to occur in a given random model. As the degree of the generators grow, we asymptotically almost surely predict projective dimension and Cohen-Macaulayness of monomial ideals, adding to previous work on Krull dimension. Another approach is to use machine learning to allow a computer to make predictions. We train neural networks to estimate Krull dimension and projective dimension of monomial ideals with good accuracy. This is joint work with Jesus de Loera, Serkan Hosten, Lily Silverstein, and Zekai Zhao.

Antonio Lerario
Scuola Internazionale Superiore di Studi Avanzati (SISSA)
A probabilistic point of view on Hilbert's Sixteenth problem
Hilbert's 16th problem was posed by David Hilbert at the Paris ICM in 1900 and, in its general form, asks for the study of the maximal number and the possible arrangements of the components of a generic real algebraic hypersurface of degree d in real projective space. This is an extremely complicated problem already for the case of plane curves: the possibilities for the arrangement of the components of such curves grow super-exponentially as the degree goes to infinity. (Notice that the same problem over the complex numbers has a simple solution.) An interesting approach is to look at this problem from the probabilistic point of view, by replacing the word "generic" with the world "random". What is the structure of a random plane curve of degree d? And how is it embedded in the real projective plane?
In these lectures I will introduce some tools which can be used for the study of this problem, combining a bit of representation theory, differential topology and asymptotic geometry. These tools are quite general and quantitative in their nature. Rather than presenting a list of results, I will try to suggest a general way of thinking where they can be effectively used.

Uwe Nagel
University of Kentucky
Lefschetz Properties and h-vectors of Graded Artinian Algebras
A standard graded algebra A over a field is said to have the weak Lefschetz property (WLP) if it contains a degree one element such that multiplication by from one degree component of A to the next always has maximal rank. In this case the Hilbert function or h-vector of A is unimodal. This vector records the vector space dimensions of the graded components of A. Even in the case that the relations of A are given by monomials such an algebra may fail the WLP or have a non-unimodal h-vector. Computer experiments suggests that algebras with these properties are rather rare. We discuss classes of randomly generated monomial algebras whose expected h-vectors are unimodal.

Michael Stillman
Cornell University
Quadratic Gorenstein rings and the Koszul property
An artinian local ring (R,m) is called Gorenstein, if it has a unique minimal ideal. If R is graded, then it is called Koszul if R∕m has linear R-free resolution. Any Koszul algebra is defined by quadratic relations, but the converse is false, and no one knows a finitely computable criterion. Both types of rings occur in many situations in algebraic geometry and commutative algebra, and in many cases, a Gorenstein quadratic algebra coming from geometry is often Koszul (e.g. homogeneous coordinate rings of most canonical curves). In 2001, Conca, Rossi, and Valla asked the question: must a (graded) quadratic Gorenstein algebra of regularity 3 be Koszul? I will talk about techniques for deciding whether a quadratic Gorenstein algebra is Koszul and methods for generating many examples which are not Koszul. We will explain how these methods provide a negative answer to the above question, as well as a complete picture in the case of regularity at least 4. (Joint work with Matt Mastroeni and Hal Schenck)

Dane Wilburne
York University
A probabilistic approach to toric ideals of phylogenetic invariants
I will show, via a probabilistic argument, that the toric ideal of phylogenetic invariants for the general group-based model on the claw tree K1,n has a quadratic Groebner basis.

Jay Yang
University of Minnesota
Degrees of Random Monomial Ideals
De Loera, Petrovic, Silverstein, Stasi, and Wilburne defined a model for a random monomial ideals inspired by the Erdos-Renyi model of random graphs. Given this model, a natural task is to understand the various invariants of an ideal. We explore the degree and related invariants of a random monomial ideal. This is joint work with Lily Silverstein and Dane Wilburne.

Sara Jamshidi Zelenberg
Illinois Institute of Technology
Machine learning for algebraists
In this talk, we present a set of techniques from machine learning relevant to algebraists with potential applications. We provide an overview of some 'best practices' used in other ML domains and provide some sample code. In addition, we demonstrate the potential with some preliminary results of ongoing work with Petrovic and Stasi. Attendees are encouraged to come with their laptops if possible.

 

Date and Location

July 01 - 04, 2019
Max Planck Institute for Mathematics in the Sciences
Inselstraße 22
04103 Leipzig
Germany

Scientific Organizers

  • Paul Breiding, Technische Universität Berlin, Institut für Mathematik
  • Jesus De Loera, University of California at Davis
  • Despina Stasi, Illinois Institute of Technology
  • Sonja Petrovic, Illinois Institute of Technology

Administrative Contact

Saskia Gutzschebauch
MPI für Mathematik in den Naturwissenschaften
Contact by Email

07.07.2019, 01:27