Seminars

Matthew Romney, Ph.D., Stevens Institute of Technology
Department Colloquium: The Metric Geometry of Surfaces

A well-known part of classical mathematics is the differential geometry of smooth surfaces, developed by historical mathematicians such as Euler and Gauss. A fundamental result on the topic is the uniformization theorem, proved by Poincaré and Koebe in 1907, which states that any smooth Riemannian surface can be mapped conformally onto a surface of constant curvature. Since then, the geometry of surfaces has been investigated in increasing generality by several research communities. Non-smooth surfaces were perhaps first systematically studied as part of the field of Alexandrov geometry beginning in the 1930s, leading to a well-developed theory of surfaces of bounded integral curvature. Surfaces also form part of the modern field of analysis on metric spaces, which has led to several striking uniformization theorems for general classes of metric surfaces. In recent work with P. Creutz and D. Ntalampekos, we show how a geometric theory of surfaces in the same spirit as Alexandrov geometry can be developed under the single minimal geometric assumption of locally finite area. In particular, we use no assumption on curvature, or any of the previous assumptions from analysis on metric spaces. As an application, we obtain a new uniformization theorem for surfaces that is essentially the strongest possible for the non-fractal setting.

Mateo Diaz, Ph.D., Johns Hopkins University
Algebra and Cryptology Center Seminar: Clustering a Mixture of Gaussians with Unknown Covariance

Clustering is a fundamental data scientific task with broad application. This talk investigates a simple clustering problem with data from a mixture of Gaussians that share a common but unknown, and potentially ill-conditioned, covariance matrix. We start by considering Gaussian mixtures with two equally-sized components and derive a Max-Cut integer program based on maximum likelihood estimation. We show its solutions achieve the optimal misclassification rate when the number of samples grows linearly in the dimension, up to a logarithmic factor. However, solving the Max-cut problem appears to be computationally intractable. To overcome this, we develop an efficient spectral algorithm that attains the optimal rate but requires a quadratic sample size. Although this sample complexity is worse than that of the Max-cut problem, we conjecture that no polynomial-time method can perform better. Furthermore, we present numerical and theoretical evidence that supports the existence of a statistical-computational gap.

Alexander Ushakov, Ph.D., Stevens Institute of Technology
Algebra and Cryptology Center Seminar: Spherical Functions: Preimage-Resistant and Collision-Free

The main goal of this work is to create bridges between problems of computational group theory (namely the problem of finding a solution for a spherical equation) and foundations of lattice-based cryptography. We introduce a family of spherical functions and demonstrate that it is preimage-resistant and collision-free, assuming that certain lattice approximation problems are hard in the worst case.

Caroline Mattes, University of Stuttgart
Algebra and Cryptology Center Seminar: Complexity of Spherical Equations in Finite Groups

Spherical equations are a special class of quadratic equations. We investigated computational properties of the Diophantine problem for spherical equations in some classes of finite groups, in particular for matrix groups. Here, the situation is quite involved: While e.g. for GL(2, p) (p prime and part of the input) it can be solved in polynomial time, for other sequences of 2-by-2 matrices like the dihedral groups it is NP-complete. Moreover, as this result suggests, we could prove that NP-completess does not transfer to super- nor sub-groups. In this talk, I will give a proof of the NP-hardness result for dihedral groups and a sketch of the proof of the polynomial time result for GL(2,p). Moreover, I will give a short overview of our further results.

Dan Pirjol, Ph.D., Stevens Institute of Technology
Department Colloquium: The Hartman-Watson Distribution: Numerical Evaluation and Applications

The Hartman-Watson distribution appears in several problems of applied probability and financial mathematics. Most notably, it determines the joint distribution of the time-integral of a geometric Brownian motion and its terminal value. A classical result by Yor (1992) expresses it as a one-dimensional integral which is however challenging to evaluate numerically in the region of interest for financial applications. The talk starts with an introduction to the Hartman-Watson distribution and presents an efficient method for its numerical evaluation using a saddle point expansion. Two applications from mathematical finance are discussed: Asian options pricing in the Black-Scholes model, and option pricing in the log-normal SABR model. Joint work with Peter Nandori (Yeshiva U.) and Lingjiong Zhu (Florida State University).

Motiejus Valiunas, Ph.D., University of Wrocław
Algebra and Cryptology Center Seminar: Spherical Functions: Trace Monoids and RAAGs in One-Relator Groups

A right-angled Artin group (RAAG; resp. a trace monoid) is a finitely presented group (resp. monoid) in which all relations are those making some pairs of the generators commute. Embeddings of trace monoids in one-relator groups have been recently studied in order to construct one-relator groups with undecidable submonoid and prefix membership problems. In an attempt to describe one-relator groups with undecidable rational subset membership problem, the following question arose: does there exist a one-relator group containing the trace monoid whose defining graph is the path of length 3, but not the corresponding RAAG? In this talk, I will explain why the answer is "no", even if the path of length 3 is replaced by any finite tree.

Corentin Bodart, University of Geneva
Algebra and Cryptology Center Seminar: Spherical Functions: Membership Problems in Nilpotent Groups

The talk will focus on the Submonoid and the Rational Subset Membership problems in nilpotent groups. Whereas the Subgroup Membership is decidable in all nilpotent groups by a classical result of Malcev, both of our problems are undecidable in large enough nilpotent groups by results of Romanikov, putting nilpotent groups on the boundary between decidability and undecidability. I’ll explain a non-obvious link between the two problems. Most importantly, this link can be used to prove the existence of a nilpotent group with decidable Submonoid Membership and undecidable Rational Subset Membership. I’ll also give some ideas on how to solve both problems in a few more groups, including the Rational Subset Membership for the 3-dimensional Heisenberg group.

Chloe Weiers, Stevens Institute of Technology
PhD Proposal Defense: The Diophantine Problem for Quadratic Equations in Wreath Products

This work focuses on the computational complexity of the Diophantine problem for orientable and non-orientable quadratic equations over wreath products of finitely generated abelian groups. The Diophantine problem for quadratic equations naturally generalizes fundamental (Dehn) problems of group theory such as the word and conjugacy problems. Furthermore, there is a deep relationship between quadratic equations and compact surfaces, which makes quadratic equations an interesting object of study. In this work, we aim to provide a complete classification of cases, depending on the relationship between characteristics of the top group and characteristics (such as genus) of a given equation, when the Diophantine problem is NP-complete or polynomial-time decidable. Additionally, potential applications of quadratic equations and associated spherical functions to group-based cryptography will be explored.

Benjamin Steinberg, Ph.D., City College of New York and the CUNY Graduate Center
Algebra and Cryptology Center Seminar: The Topological Approach to the Semigroup Homology

The speaker and Robert Gray have developed a topological approach to semigroup homology. Our initial motivation was to attack Kobayashi's problem from 2000 as to whether all one-relator semigroups are type FP-infinity. While the main application of our theory was to answer positively Kobayashi's question, the theory is also useful for other purposes. In this talk I'll sketch a topological proof of Pride's unpublished generalization to semigroups of the classical result relating deficiency to the Schur multiplier. I'll also use topological means to give a complete computation of the homology of a completely simple semigroup. Previously, there was a computation of the Schur multiplier for finite simple semigroups and some results about high dimensional cohomology by Nico.

Murray Elder, Ph.D., University of Technology Sydney
Algebra and Cryptology Center Seminar: A New Type of Pumping Lemma for Multiple Context Free Languages

I will explain a new substitution lemma for proving that a language is not multiple context-free. This is joint work with Andrew Duncan and Mengfan Lyu.

Ilya Kapovich, Ph.D., Hunter College of the City University of New York
Algebra and Cryptology Center Seminar: On Two-Generator Subgroups of Mapping Torus Groups

Motivated by the results of Jaco and Shalen about 3-manifold groups, we prove that if F is a free group (of possibly infinite rank), $\phi: F\to F$ is an injective endomorphism of $\phi$ and $G_\phi=\langle F,t| t x t^{-1} =\phi(x), x\in F\rangle$ is the mapping torus group of $\phi$ then every two-generator subgroup of $G_\phi$ is either free or a “sub-mapping torus.” For a fully irreducible automorphism $\phi$ of a finite rank free group $F_r$ this result implies that every two-generator subgroup of the free-by-cyclic group $G_\phi$ is either free, free abelian, a Klein bottle group or a subgroup of finite index in $G_\phi$; and if $\phi\in Out(F_r)$ is fully irreducible and atoroidal then every two-generator subgroup of $G_\phi$ is either free or of finite index in $G_\phi$. This talk is based on joint work with Naomi Andrew, Edgar A. Bering IV and Stefano Vidussi.