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).
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.
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.
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)
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.
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.
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.
Rida Ait El Manssour Università degli Studi di Trieste, ItalyOn the number of real lines on random invariant cubic surfaces
It is a classical result in algebraic geometry that there are exactly 27 complex lines on a smooth cubic surface in three-dimensional projective space. If the cubic surface is defined by a real equation, the number of real lines on it depends on the coefficients of this equation (generically there could be 3, 7, 15 or 27). In this context, it is natural to ask for the expected number of real lines, by letting the defining equation be a random polynomial. In this direction Basu, Lerario, Lundberg and Peterson have recently proved that if the polynomial is uniformly sampled from the Bombieri-Weil distribution, the expected number of real lines on this cubic is 6\sqrt{2}-3. The Bombieri-Weil distribution is however just a single instance of a one dimensional family of probability distributions on the space of polynomials which are invariant under orthogonal change of variables (i.e. for which there are no preferred points or directions in the projective space for the corresponding zero set). In this work, we study the average number of real lines for all the elements of this family and prove that the maximal expectation is reached by random purely harmonic polynomials.
Rida Ait El Manssour Università degli Studi di Trieste, ItalyOn the number of real lines on random invariant cubic surfaces
It is a classical result in algebraic geometry that there are exactly 27 complex lines on a smooth cubic surface in three-dimensional projective space. If the cubic surface is defined by a real equation, the number of real lines on it depends on the coefficients of this equation (generically there could be 3, 7, 15 or 27). In this context, it is natural to ask for the expected number of real lines, by letting the defining equation be a random polynomial. In this direction Basu, Lerario, Lundberg and Peterson have recently proved that if the polynomial is uniformly sampled from the Bombieri-Weil distribution, the expected number of real lines on this cubic is 6\sqrt{2}-3. The Bombieri-Weil distribution is however just a single instance of a one dimensional family of probability distributions on the space of polynomials which are invariant under orthogonal change of variables (i.e. for which there are no preferred points or directions in the projective space for the corresponding zero set). In this work, we study the average number of real lines for all the elements of this family and prove that the maximal expectation is reached by random purely harmonic polynomials.
Carlos Améndola TU Munich, GermanyAutocovariance Varieties of Moving Average Random Fields
We study the autocovariance functions of moving average random fields over the integer lattice \mathbb{Z}^d from an algebraic perspective. These autocovariances are parametrized polynomially by the moving average coefficients, hence tracing out algebraic varieties. We derive dimension and degree of these varieties and we use their algebraic properties to obtain statistical consequences such as identifiability of model parameters. We connect the problem of parameter estimation to the algebraic invariants known as euclidean distance degree and maximum likelihood degree. Throughout, we illustrate the results with concrete examples. In our computations we use tools from commutative algebra and numerical algebraic geometry.
Mara Belotti Università degli Studi di Trieste, ItalyOn the number of real lines on random invariant cubic surfaces
It is a classical result in algebraic geometry that there are exactly 27 complex lines on a smooth cubic surface in three-dimensional projective space. If the cubic surface is defined by a real equation, the number of real lines on it depends on the coefficients of this equation (generically there could be 3, 7, 15 or 27). In this context it is natural to ask for the expected number of real lines, by letting the defining equation be a random polynomial. In this direction Basu, Lerario, Lundberg and Peterson have recently proved that if the polynomial is uniformly sampled from the Bombieri-Weil distribution, the expected number of real lines on this cubic is The Bombieri-Weil distribution is however just a single instance of a one dimensional family of probability distributions on the space of polynomials which are invariant under orthogonal change of variables (i.e. for which there are no preferred points or directions in the projective space for the corresponding zero set). In this work we study the average number of real lines for all the elements of this family and prove that the maximal expectation is reached by random purely harmonic polynomials. (This is the starting case of a more general approach that we plan to investigate in the future, for constructing real hypersurfaces of degree 2n-3 in real projective space of dimension n with many lines on them by simply sampling them randomly from an appropriate distribution.)
Some normalized integral inequalities in Statisitc and Probability
In this poster, we present recent results on some normalized integral inequalities for continuous random variables via Riemann-Liouville integration. Some classical results are generalized and some applications are discussed.
Oliver Gäfvert KTH Royal Institute of Technology, SwedenComplexity of variety learning
Extracting structure from a point cloud is a fundamental problem in data analysis, and when this structure is coming from polynomial equations we can use the machinery of algebraic geometry. We study the set of closest real algebraic hypersurfaces to a finite set of points, and investigate methods to approximate the closest hypersurface of a given degree. We investigate the complexity of this problem by considering the Euclidean Distance Degree (EDD) of the variety of point configurations lying on a hypersurface of a given degree and how the complexity depends on the number of points in the configuration.
Alexandros Grosdos Koutsoumpelias Universität Osnabrück, GermanyAlgebraic statistics of local Dirac mixture moments
Leo Mathis SISSA, ItalyReal Schubert Problems and the Segre Zonoid
I will present recent work in integral geometry in the real Grassmannian. I will explain how random real Schubert problem can be linked with the volume of special convex bodies, namely zonoids. I will show how this allows us to establish asymptotic formulae.This is a joint work with Antonio Lerario and Peter Bürgisser.
Chiara Meroni Università degli Studi di Trieste, ItalyOn the number of real lines on random invariant cubic surfaces
It is a classical result in algebraic geometry that there are exactly 27 complex lines on a smooth cubic surface in three-dimensional projective space. If the cubic surface is defined by a real equation, the number of real lines on it depends on the coefficients of this equation (generically there could be 3, 7, 15 or 27). In this context it is natural to ask for the expected number of real lines, by letting the defining equation be a random polynomial. In this direction Basu, Lerario, Lundberg and Peterson have recently proved that if the polynomial is uniformly sampled from the Bombieri-Weil distribution, the expected number of real lines on this cubic is 6\sqrt{2}-3. The Bombieri-Weil distribution is however just a single instance of a one dimensional family of probability distributions on the space of polynomials which are invariant under orthogonal change of variables (i.e. for which there are no preferred points or directions in the projective space for the corresponding zero set). In this work we study the average number of real lines for all the elements of this family and prove that the maximal expectation is reached by random purely harmonic polynomials.
Frank Röttger OVGU Magdeburg, GermanyAsymptotics of a locally dependent statistic on finite reflection groups
We discuss the asymptotic behaviour of the number of descents in a random signed permutation and its inverse, which was posed as an open problem by Chatterjee and Diaconis in a recent publication. For that purpose, we generalize their result for the asymptotic normality of the number of descents in a random permutation and its inverse to other finite reflection groups. This is achieved by applying their proof scheme on signed permutations, so elements of Coxeter groups of type B, which is also known as the hyperoctahedral group. Furthermore, a similar central limit theorem for elements of Coxeter groups of type D is derived via Slutsky's Theorem and a bound on the Wasserstein distance of certain normalized statistics with local dependency structures and bounded local components is proven for both types of Coxeter groups.
Liam Solus KTH Royal Institute of Technology, SwedenInterventional Markov Equivalence for Mixed Graph Models
We will discuss the problem of characterizing Markov equivalence of graphical models under general interventions. Recently, Yang et al. (2018) gave a graphical characterization of interventional Markov equivalence for DAG models that relates to the global Markov properties of DAGs. Based on this, we extend the notion of interventional Markov equivalence using global Markov properties of loopless mixed graphs and generalize their graphical characterization to ancestral graphs. On the other hand, we also extend the notion of interventional Markov equivalence via modifications of factors of distributions Markov to acyclic directed mixed graphs. We prove these two generalizations coincide at their intersection; i.e., for directed ancestral graphs. This yields a graphical characterization of interventional Markov equivalence for causal models that incorporate latent confounders and selection variables under assumptions on the intervention targets that are reasonable for biological applications.
Michele Stecconi SISSA, ItalyThe expected topology of the singular locus of Kostlan random polynomials
We study the set of points on the m-dimensional Sphere at which a homogenous polynomial attains a given nondegenerate singularity, i.e. points where the r-jet prolongation of the polynomial meets transversally some given semialgebraic submanifold of the space of r-jets. The topology of the singular locus is thought as the data of the m+1 vector of its Betti numbers.I will present a recent result which establishes that in the Kostlan case, under reasonable hypothesis on the singularity, the expected value of each Betti number grows like d^(m/2), namely like the square root of the corresponding deterministic upper bound, as the degree d of the polynomial tends to infinity. This phenomena is justified by the fact that the restriction of a Kostlan polynomial to an affine disk of radius ~d^(-1/2) converges as a random field in a very strong way.
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.
A standard graded algebra $A$ over a field is said to have the weak Lefschetz property (WLP) if it contains a degree one element $\ell$ such that multiplication by $\ell$ 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.
I will show, via a probabilistic argument, that the toric ideal of phylogenetic invariants for the general group-based model on the claw tree $K_{1,n}$ has a quadratic Groebner basis.
Participants
Zachary Adams
MPI MiS
Daniele Agostini
Humboldt-Universität zu Berlin
Rida Ait El Manssour
Università degli Studi di Trieste
Carlos Améndola
TU Munich
Mara Belotti
Università degli Studi di Trieste
Matías Bender
TU Berlin
Paul Breiding
Technische Universität Berlin
Juliette Bruce
University of Wisconsin - Madison
Winfried Bruns
Universität Osnabrück
Peter Buergisser
Technische Universität Berlin
Türkü Özlüm Çelik
MPI MIS
Jin-San Cheng
KLMM, Academy of Mathematics and Systems Science, CAS
Yairon Cid Ruiz
University of Barcelona
Colin Crowley
University of Wisconsin -- Madison
Jesus De Loera
University of California at Davis
Mahmut Levent Doğan
TU Berlin
Eliana Duarte
MPI Leipzig - OVGU
Timothy Duff
Georgia Institute of Technology
Christian Eder
University of Leipzig
Daniel Erman
University of Wisconsin-Madison
Oliver Gäfvert
KTH Royal Institute of Technology
Paul Görlach
Max Planck Institute MiS Leipzig
Alexandros Grosdos Koutsoumpelias
Universität Osnabrück
Marc Härkönen
Georgia Tech
Serkan Hosten
San Francisco State University
Jaewoo Jung
Georgia Institute of Technology
David Kahle
Baylor University
Nidhi Kaihnsa
MPI MIS
Robert Krone
University of California, Davis
Kisun Lee
Georgia Tech
Antonio Lerario
Scuola Internazionale Superiore di Studi Avanzati (SISSA)
András Lőrincz
Max Planck Institute for Mathematics in the Sciences
Madhusudan Manjunath
Indian Institute of Technology Bombay
Aida Maraj
University of Kentucky
Leo Mathis
SISSA
Chiara Meroni
Università degli Studi di Trieste
Uwe Nagel
University of Kentucky
Andrew Newman
TU Berlin
Julius Niemeyer
University of Leipzig
Amir Niknejad
Mount Saint Vincent
Alessandro Oneto
OVGU Magdeburg
Junyoung Park
Korea Advanced Institute of Science and Technology
Dylan Peifer
Cornell University
Sonja Petrovic
Illinois Institute of Technology
Yue Ren
MPI MIS
Jose Rodriguez
University of Wisconsin --- Madison
Tim Römer
Universität Osnabrück
Frank Röttger
OVGU Magdeburg
Francisco Santos
Universidad de Cantabria
Peter Schenzel
Martin-Luther University Halle-Wittenberg
Liam Solus
KTH Royal Institute of Technology
Miruna-Stefana Sorea
Max Planck Institute for Mathematics in the Sciences
Despina Stasi
Illinois Institute of Technology
Michele Stecconi
SISSA
Michael Stillman
Cornell University
Bernd Sturmfels
Max Planck Institute for Mathematics in the Sciences
Maddie Weinstein
UC Berkeley
Dane Wilburne
York University
Jay Yang
University of Minnesota
Sara Jamshidi Zelenberg
Illinois Institute of Technology
Scientific Organizers
Paul Breiding
Technische Universität Berlin
Jesus De Loera
University of California at Davis
Despina Stasi
Illinois Institute of Technology
Sonja Petrovic
Illinois Institute of Technology
Administrative Contact
Saskia Gutzschebauch
Max-Planck-Institut für Mathematik in den Naturwissenschaften
Contact via Mail