ACC Seminar

Room 316, North Building, 4pm, refreshments at 3:30. Campus map Zoom: https://stevens.zoom.us/j/93228680142 Password: ACC

Fall 2024 ⤵

Monday Dec 2	Speaker: Russell Miller (Queens College CUNY) Title: Interpreting a field in its Heisenberg group Abstract: The Heisenberg group G(F) of a field F is the group of upper triangular matrices in GL_3(F), with 1's along the diagonal and 0's below it. This group is obviously interpretable (indeed definable) in the field F. Mal'cev showed that one can recover F from G(F), and indeed that there is an interpretation of F in G(F) using two parameters. Any two noncommuting elements of G(F) can serve as the parameters, but Mal'cev was unable to produce an interpretation without parameters. After introducing the notions of a computable functor and an effective interpretation, we will present joint work showing that there is an effective interpretation of each countable field in its Heisenberg group, without parameters, uniformly in F. (That is, the same formulas give the interpretation, no matter which field F we consider.) Moreover, from the effective interpretation we will then extract a traditional interpretation without parameters, in the usual model-theoretic sense. Finally we will note that, whereas Mal'cev's result actually gives a definition of F in G(F), there is no parameter-free definition of F there. This work is joint with Rachael Alvir, Wesley Calvert, Grant Goodman, Valentina Harizanov, Julia Knight, Andrey Morozov, Alexandra Soskova, and Rose Weisshaar.
Monday Nov 18	Speaker: Eilidh McKemmie (Kean University) Title: Finite simple groups in cryptography Abstract: We discuss two different factorization problems involving finite simple groups. First we consider approaches to searching in Cayley graphs and applications to hash functions. Then we will define logarithmic signatures and an associated rewriting problem which appears in several proposed public-key cryptosystems.
Monday Nov 11	Speaker: Jerry Shen (University of Technology Sydney) Title: The complexity of the epimorphism problem with virtually abelian and finite dihedral targets. Abstract: Friedl and Loh showed that the epimorphism problem for certain subclasses of virtually abelian targets is decidable. Separately, Kuperberg and Samperton showed that the epimorphism problem from certain 3-manifold groups to finite non-abelian simple groups is NP-hard. In this talk I will show that the epimorphism problem from finitely presented groups to virtually abelian to the same subclasses of virtually abelian groups is in NP, and to finite non-nilpotent dihedral groups is also NP-hard.
Monday Nov 4	Speaker: Matthew Romney (Stevens) Title: Hausdorff dimension and quasisymmetric mappings. Abstract: Hausdorff dimension is a standard notion of dimension for arbitrary metric spaces. Quasisymmetric maps are a natural generalization of conformal mappings in complex analysis to the setting of metric spaces. In this talk, we examine the interaction of these two concepts. A problem of wide interest is to determine when the Hausdorff dimension of a metric space can be lowered by applying a quasisymmetric map. For some spaces (e.g., Sierpinski carpets and gaskets) this can be done; for others (e.g., many product spaces) this is not possible. As our main result, we show how to construct quasisymmetric maps that lower dimension for positive-measure subsets of R^n, and give applications of this construction.
Monday Oct 28	Speaker: Jie Shen (Stevens) Title: Some Optimal Results in Robustness Classification . Abstract: Learning linear classifiers (i.e. halfspaces) is one of the fundamental problems in machine learning dating back to 1950s. In the presence of benign label noise such as random classification noise, the problem is well understood. However, when the data are corrupted by more realistic noise, even establishing polynomial-time learnability can be nontrivial. In this talk, I will introduce our recent work on learning with malicious noise (a.k.a. data poisoning attack) where an adversary may inspect the learning algorithm and may inject malicious data. We present the first sample-optimal learning algorithm that achieves information-theoretic noise tolerance under logconcave distributional assumptions. We further show that when clean data are separable with a small margin, there exists linear-time learning algorithm with constant noise tolerance.
Monday Oct 21	Speaker: Daniel Bossaller (University of Alabama in Huntsville) Title: Algebraic Methods In Distributed Storage. Abstract: With the advent of cloud storage, big data, and social media, it is important to store user files across many computers/drives in such a way that guards against data loss/corruption. However, a greater resilience against data loss requires more storage space on the network, forcing a compromise. Furthermore, if one or many of the computers storing the file is lost, it is crucial to develop efficient algorithms to replace those missing nodes while minimizing, for example, computational complexity of the repair and/or network traffic. In this talk I will survey some of the ways in which algebraic methods, such as algebraic coding theory, may be employed to achieve these goals, with a special focus on regenerating codes and Reed-Solomon codes. If time permits, I will report on my joint work with Hiram Lopez (Virginia Tech) on the exact repair problem for generalizations of Reed Solomon codes and possible applications to other areas of information theory and theoretical computer science.
Monday Oct 7	Speaker: Alexei Miasnikov (Stevens) Title: Abstract isomorphisms, rigidity, and bi-interpretability. Abstract: In this talk I will show that quite often behind various "rigidity phenomena" one can find a bi-interpretation/interpretation of algebraic structures. These rigidity phenomena include typical results on coordinatization, rigidity theorems, equivalence of categories, and “abstract isomorphisms”. The hidden bi-interpretation/interpretation usually gives the most precise and robust description of the phenomenon. In particular, I will discuss in more detail the fundamental theorems of geometry, Malcev’s correspondence between nilpotent groups and nilpotent Lie algebras, and abstract isomorphisms of algebraic groups.

Spring 2024 ⤵

Monday Apr 29	Speaker: Ilya Kapovich (Hunter College CUNY) Title: On two-generator subgroups of mapping torus groups Abstract: 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 \mid tx 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.
Monday Apr 22	Speaker: Murray Elder (University of Technology Sydney) Title: A new type of pumping lemma for multiple context free languages. Abstract: 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.
Monday Apr 15	Speaker: Benjamin Steinberg (City College CUNY) Title: The topological approach to the semigroup homology. Abstract: The speaker and Robert Gray have a 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.
Monday Apr 1	Speaker: Turbo Ho (California State University Northridge) Title: Decision problem for groups as equivalence relations. Abstract: In 1911, Dehn proposed three decision problems for finitely presented groups: the word problem, the conjugacy problem, and the isomorphism problem. These problems have been central to both group theory and logic, and were each proven to be undecidable in the 50s. There is much current research studying the decidability of these problems in certain classes of groups. Classically, when a decision problem is undecidable, its complexity is measured using Turing reducibility. However, Dehn's problems can also be naturally thought of as computably enumerable equivalence relations (ceers). We take this point of view and measure their complexity using computable reductions. This yields behaviors different from the classical context: for instance, every Turing degree contains a word problem, but not every ceer degree does. This leads us to study the structure of ceer degrees containing a word problem and other related questions. This is a joint work with Uri Andrews, Matthew Harrison-Trainor, and Luca San Mauro.
Monday Mar 25	Speaker: Corentin Bodart Title: Membership problems in nilpotent groups. Abstract: 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.
Monday Mar 18	Speaker: Motiejus Valiunas Title: Trace monoids and RAAGs in one-relator groups. Abstract: 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. This is joint work with Ashot Minasyan.
Monday Mar 4	Speaker: Caroline Mattes Title: Complexity of Spherical Equations in Finite Groups. Abstract: 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.
Monday Feb 26	Speaker: Alexander Ushakov Title: Spherical functions: preimage-resistant and collision-free. Abstract: 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.
Monday Feb 12	Speaker: Mateo Diaz Title: Clustering a mixture of Gaussians with unknown covariance. Abstract: 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.

Fall 2023 ⤵

Monday Dec 4	Speaker: Saadet Oyku Yurttas (Dicle University, Turkey) Title: Computations in braid groups with Dynnikov coordinates Abstract: Dynnikov coordinates put global coordinates on the space of measured foliations on an n-times punctured disk. In this talk, I will survey Dynnikov coordinates and investigate how we use this coordinate system to study pseudo–Anosov braids making use of results from Thurston's theory on surface homeomorphisms. Then, I will discuss joint work with Daniele Alessandrini which generalizes the techniques used in the case of the n-punctured disk to higher genus surfaces with finitely many punctures.
Monday Nov 27	Speaker: Anna Erschler (Ecole Normale Superieure) Title: What makes an infinite group small? Abstract: Given two finitely generated groups, one can ask which of them is asymptotically larger than the other. There are many asymptotic invariants that can measure this largeness: growth function, Foelner function, various invariants related to random walks. There are known inequalities between such invariants, but in general the asymptotics of one invariant does not define the others. There is a rich variety for behavior of the invariants unless we are in the class of groups that are in some sense "smallest", and in the latter situation one can expect algebraic conclusions about these groups. I will make a survey of known phenomena and open questions in this domain, and explain some recent results.
Monday Nov 13	Speaker: Eric Ramos (Stevens) Title: Explicit computations of the homologies of complete graph braid groups through quantitative representation stability Abstract: Given a graph G, its n-pointed configuration space is the topological space of n distinct points on G. The n-stranded braid group of G is then defined to be the fundamental group of this space. Despite having been studied for decades, very little is known about these groups. In this talk, we will look at new computations of the homologies of the braid groups of the complete graphs. These computations were completed using the theory of representation stability. More specifically, we use the theory of representation stability to determine when these homologies must begin to display a certain kind of regularity, then use computer algebra systems to compute all of the homologies before this point.
Monday Nov 6	Speaker: Johanna Franklin (Hofstra) Title: Generalizing a question of Gromov Abstract: When Gromov asked "What is a typical group?", he was thinking of finitely presented groups, and he proposed an approach involving limiting density. Here, we reframe this question in the context of universal algebra and discuss some examples illustrating the behaviors of some of these algebraic varieties and then general conditions that imply some of these behaviors. Our primary general result states that for a commutative generalized bijective variety and presentations with a single generator and single identity, the zero-one law holds and, furthermore, that the sentences with density 1 are those true in the free structure. The proof of this result requires a specialized version of Gaifman's Locality Theorem that enables us to get a better bound on the complexity of the formulas of interest to us. This work is joint with Meng-Che "Turbo" Ho and Julia Knight.
Monday Oct 30	Speaker: Daniele Alessandrini (Stevens) Title: Group actions on homogeneous spaces Abstract: Homogeneous spaces are spaces with lots of symmetries, where every point has the same properties. Most classical geometric spaces are homogeneous spaces. I will discuss some ways to construct interesting geometric actions of certain hyperbolic groups on homogeneous spaces. These actions have interesting dynamical properties. I will present some recent results that describe the geometry of these actions.
Monday Oct 23	Speaker: Elidh McKemmie (Rutgers-New Brunswick) Title: Galois groups of random additive polynomials Abstract: The Galois group of an additive polynomial over a finite field is contained in a finite general linear group. We will discuss three different probability distributions on these polynomials, and estimate the probability that a random additive polynomial has a "large" Galois group. Our computations use a trick that gives us characteristic polynomials of elements of the Galois group, so we may use our knowledge of the maximal subgroups of GL(n,q). This is joint work with Lior Bary-Soroker and Alexei Entin.
Monday Oct 16	Speaker: Rylee Lyman (Rutgers-Newark) Title: Exploring deformation spaces of tree actions Abstract: Many groups act on trees. In fact, Bass and Serre's theory of graphs of groups allows one to easily construct new groups from old equipped with interesting actions on trees. When a group acts on a tree, it typically does so in many ways. For example, one may consider "twisting" the action by an endomorphism of the group. The purpose of this talk is to introduce Forester and Guirardel–Levitt's deformation spaces of group actions on trees. For some tree actions, this may be profitably be thought of as a tree-theoretic analogue of the Teichmüller space of a finite-type surface. I will attempt to state some results of mine as well as some questions I find interesting.
Thurs. Oct 12	Speaker: Vladimir Shpilrain (City College, CUNY) Title: Tropical cryptography Abstract: An obvious advantage of using tropical algebras (a.k.a. min-plus algebras) as platforms for cryptographic primitives is unparalleled efficiency of computation because in tropical schemes, one does not have to perform any multiplications of numbers since tropical multiplication is the same as the usual addition. In this talk, I will briefly survey some previous proposals (joint with Dima Grigoriev) of public key exchange and encryption schemes, and then will focus on a new digital signature protocol (joint with Jiale Chen and Dima Grigoriev) whose security is based on computational hardness of factoring one-variable tropical polynomials; this problem is known to be NP-hard.

Spring 2023 ⤵

Monday May 8	Speaker: Alexei Miasnikov (Stevens) Title: Computational group theory: practical algorithms or complexity classes? Abstract: In this talk I will discuss an old point of tension in algorithmic group theory: what is more important, to create a practical algorithm that can solve an algorithmic problem on some rather large inputs in a reasonable time or to prove that a problem at hands belongs to a nice complexity class by providing a theoretically fast algorithm, which may not be practical at all?
Monday May 1	Speaker: Chloe Weiers (Stevens) Title: Quadratic equations in wreath products Abstract: We discuss complexity of solving quadratic equations, focusing first on the standard lamplighter group and generalizing to restricted wreath products of finitely generated abelian groups. We provide a classification of cases, depending on the relationship between characteristics of the top group and characteristics (such as genus) of a given equation, when the problem is NP-complete or polynomial-time decidable. Connections with the tiling problem are also discussed. Based on joint work with A. Ushakov.
Monday April 24	Speaker: Armin Weiß (Universität Stuttgart) Title: The Power Word Problem in Graph Products Abstract: The power word problem of a group G asks whether an expression p_1^{x_1} ... p_n^{x_n}, where the p_i are words over the generators and the x_i binary encoded integers, is equal to the identity of G. Thus, the power word problem is a generalization of the word problem and a special case of the compressed word problem. This is reflected by its complexity. In the first part of the talk I will give an overview on what is known about the power word problem in different groups. The second part of the talk will focus on the power word problem in free groups and, more generally, on graph products of groups. In particular, we show that the power word problem in a fixed graph product is AC0-Turing-reducible to the word problem of the free group and the power word problem of the base groups. Furthermore, we look into the uniform power word problem in a graph product, where the dependence graph and the base groups are part of the input. Given a class of finitely generated groups C, the uniform power word problem in a graph product can be solved in AC0(C_=L^{PowWP C}). As a consequence of our results, the uniform knapsack problem in graph groups is NP-complete.
Monday April 17	Speaker: Sam Corson (Universidad del País Vasco) Title: Groups with finitary behavior Abstract: This talk will be a discussion of infinite groups which share properties with finite groups, either in their actions (strongly bounded groups) or in their relationship to proper subgroups (Jonsson groups). There will be a historical review and some recent constructions of such groups. Includes joint work with Saharon Shelah.
Monday April 10	Speaker: Lubjana Beshaj (USMA, West Point) Title: Data Poisoning and Neural Network Cryptography Abstract: Data poisoning against security software that uses artificial intelligence (AI) and machine learning (ML) is likely the next big cybersecurity risk. The security of data in a network-based computer system has become a major challenge in the world today. With the high increase in network traffic, hackers and malicious users are devising new ways of network intrusion. In this talk we will explore how we can leverage neural network cryptography, which is a relatively new area which explores different methodologies to utilize neural networks in cryptography systems, to make communication between neural networks safe and minimize network intrusions.
Monday April 3	Note: This talk starts at 4:15, not 4:00. Speaker: Vladimir Shpilrain (City College, CUNY) Title: Two digital signature schemes based on multivariate polynomials Abstract: We offer two very transparent digital signature schemes. One of them is very simple; it uses non-square matrices over polynomials and can be converted to a public key encryption scheme. The other one is slightly more sophisticated; it is based on counting zeros of Boolean polynomials. The talk is based on joint work with Jiale Chen, Dima Grigoriev, Ilia Ilmer, and Alexey Ovchinnikov.
Monday Mar 27	Speaker: Ionut Florescu (Stevens) Title: A Sparsity Algorithm for Finding Optimal Counterfactual Explanations. Example of its application to Corporate Credit Rating Abstract: For the majority of complex Machine Learning techniques, interpreting and understanding how output responds to changes in inputs is difficult. This is the reason such techniques are often termed “Black Boxes”. A counterfactual explanation applies to an already estimated machine learning algorithm. It attempts to find the smallest modification of the input values which changes the prediction to a new output, other than the original one. In this work, we formulate the problem of finding a counterfactual explanation as an optimization problem. We propose a new “sparsity algorithm” which solves this problem, while increasing the sparsity of the counterfactual explanation (i.e., a solution to the optimization problem). We validate the newly introduced sparsity algorithm with synthetically generated data and we further apply it to quarterly financial statements from companies in the US market. We provide evidence that the counterfactual explanation can capture the majority of features that changed between two quarters when ratings improve. The results obtained show that the higher the rating of a company, the greater the “effort” required to further improve credit rating. The goal of this talk is to use the credit rating as an example, and to highlight the methodology. We believe the sparsity algorithm may be applicable in a much wider context.
Monday Mar 20	Speaker: Jennifer Taback (Bowdoin) Title: A new proof of the growth rate of BS(1,n) Abstract: In joint work with Alden Walker, we give a new proof of the growth rate of the solvable Baumslag-Solitar groups BS(1,n). When n>2 is even, the polynomials we encounter are much simpler than those used in previous computations of this growth rate. Motivated by a question from Moon Duchin, Alden Walker and I investigated a new notion of discrete curvature for Cayley graphs in the case of BS(1,n), which necessitated a detailed understanding of geodesics. As part of that work, we realized that a subset of the geodesic paths we were constructing formed a regular language and could be used to compute the growth rate of BS(1,n).
Monday Feb 6	Speaker: Alina Vdovina, City College, CUNY) Title: *Higher structures in mathematics: buildings, k-graphs and C-algebras Abstract:** We present buildings as universal covers of certain infinite families of CW-complexes of arbitrary dimension. We will show several different constructions of new families of k-rank graphs and C*-algebras based on these complexes, for arbitrary k. The underlying building structure allows explicit computation of the K-theory as well as the explicit spectra computation for the k-graphs.

Fall 2022

Monday Dec 5	Speaker: Upendra Prasad (Stevens) Title: Some Applications of Randomized Numerical Algorithms in Data Science Abstract: Randomized numerical linear algebra offers some state-of-the-art algorithms to solve big data problems. We will inquire into some typical applications arising in dimensionality reduction, especially in computer vision. We will explore the intuitive idea behind some randomized algorithms for solving these problems and discuss the underlying theoretical framework.
Monday Nov 21	Speaker: Monika (Stevens) Title: The Numerical Index of a Banach space Abstract: The numerical index, n(X), of a Banach space, X, is a number relating the norm and the numerical range of a bounded linear operator. The problem of computing the numerical index of the L_p spaces has been latent since the beginning of the theory. In this talk I will start with the basics of the numerical index and will show that n(l^2_p) = sup_t∈[0,1] \|t^(p−1) − t\|/(1 + t^p) for p ∈ [1.4547, 3.19925]. This result is an extension of the result by Javier Merı and Alicia Quero. Other recent results will also be discussed.
Monday Nov 14, 2022.	Speaker: Robert Gilman Title: Formal Languages and Groups (Stevens) Abstract: This is an expository talk with open questions on connections between formal language theory and group theory.
Monday Nov 7, 2022	Speaker: Denis Ovchinnikov (Cornami Inc.) Title: Fully Homomorphic Encryption - an overview Abstract: Fully Homomorphic Encryption (FHE) is a class of encryption schemes that allow performing operations on encrypted data without the need to decrypt intermediate results, thus making them extremely valuable in many real-life applications. Although several theoretical schemes have been known since 2009 (Gentry), all known approaches are extremely slow and can not currently be used on a large scale. Interestingly, most FHE schemas are based on learning with errors (LWE) and ring learning with errors (RLWE) making them not only important in practice but also fascinating from an algebraic point of view. I will provide an outline of FHE schemas setup, illustrate how they allow performing homomorphic operations in encrypted form, explain common security assumptions, and mention challenges in using such schemas in practice. I will use the tFHE schema as an example, but many ideas are common between several schemas.
Monday Oct 31, 2022	Speaker: Benjamin Leinwand (Stevens) Title: Augmented Degree Correction for Binary Networks Abstract: Modeling networks can serve as a means of summarizing the processes underpinning high-dimensional complex systems. Adapting an approach initially devised for dense weighted networks, this work (in progress) proposes a new method for generating and estimating unweighted networks. Each edge is a Bernoulli random variable with probability that is a composition of a linear function of community memberships with a nonlinear function of nodal parameters. As edges can take on only 0/1 values, the signal is less precise than in the case with continuous weights, posing additional challenges to estimating the edge probabilities. However, restricting to the binary case permits the use of likelihood-based estimation techniques, which can also improve estimation of nodal features.
Monday Oct 24	Speaker: Paul Schwartz (Stevens) Title: Galois scaffolds and Galois module structure for totally ramified C^2_p-extensions in characteristic 0. Abstract: The normal basis theorem states that if L/K is a Galois extension of fields with Galois group G, then L is a free module of rank one over the group algebra K[G]. Naturally, number theorists asked, is there such a thing as an integral basis theorem? That is to say, if L/K is a Galois extension of number fields, with ring of integers Ints_L and Ints_K respectively, is Ints_L free over Ints_K? Over the past decade, the theory of Galois scaffolds has been developed and applied to this question in the characteristic p case. We translate this work into the setting of characteristic 0.
Monday Oct 17	Speaker: Alexander Ushakov (Stevens) Title: Kyber public key encryption Abstract: We discuss the basics of Kyber -- one of the first finalists in the NIST post-quantum cryptography project. Its security is based on the hardness of solving the learning-with-errors (LWE) problem over module lattices. This talk is suitable for non-experts.
Monday Sept 26	Speaker: Alexei Miasnikov (Stevens) Title: General algebraic schemes, non-standard groups, and first-order classification Abstract: In this talk I will discuss a new notion of an algebraic group scheme and the related class of "new” algebraic groups (which, of course, contains the classical ones). This leads to some interesting results on the first-order classification problems and sheds new light on first-order rigidity and quasi finite axiomatization. In another direction I will touch on non-standard models of groups (aka non-standard analysis), in particular, non-standard models of the finitely generated ones with decidable word problems, and explain how they naturally appear as non-standard Z-points of the general algebraic groups.
Monday Sept 19	Speaker: Michael Figelius (Universität Siegen) Title: The knapsack problem for HNN-extensions, hyperbolic groups and graph products. Abstract: The knapsack problem over arbitrary, non-commutative, finitely generated groups was first stated by Myasnikov, Nikolaev and Ushakov in 2013. Since then, a lot of research has been done in this area. We provide a brief overview of what the knapsack problem actually is, and investigate groups and group constructions where the solution set of knapsack equations has a so-called semilinear structure. Of particular importance are hyperbolic groups and the two group constructions called graph product and HNN-extensions. The latter has been used to construct groups with an undecidable word problem.

Spring 2022

Monday May 17	Speaker: Vladimir Shpilrain (City College, CUNY) Title: Average-case complexity of algorithmic problems in some groups Abstract: The worst-case complexity of group-theoretic algorithms has been studied for a long time. Generic-case complexity, or complexity on random inputs, was introduced and studied relatively recently. In this talk, we address the average-case complexity of the word problem and the subgroup membership problem in several classes of groups and show that it is often the case that the average-case complexity is linear with respect to the length of an input word. The classes of groups that we consider include groups of matrices over rationals (in particular, polycyclic groups), some classes of solvable groups, as well as free products. For free products, we also address the average-case complexity of the subgroup membership problem and show that it is often linear, too. Finally, we consider the identity problem that has not been considered before, to the best of our knowledge. The talk is based on joint work (in progress) with A.Yu.Olshanskii.
Monday Apr 25	Speaker: Jan Cannizzo (Stevens) Title: Surjunctivity and false Cayley graphs Abstract: A finitely generated group G is surjunctive if every cellular automaton on G that is injective is also surjective. After reviewing some known results and open questions surrounding surjunctive groups, we will discuss generalizations of surjunctivity to other objects, notably monoids and spaces upon which monoids act. We introduce the notion of a false Cayley graph of a finitely generated group and show that among these objects, cellular automata that are injective but not surjective are abundant. This talk is based on joint work with Jonathan Cerqueira.
Monday Apr 4	Speaker: Denis Ovchinnikov (Stevens) Title: Diophantine problem in polycyclic groups. Abstract: The Diophantine problem for a group G is a problem of finding an algorithm that given a finite system of equations over G (with constants) outputs whether the system has a solution in G or not. The Diophantine problem is said to be undecidable if no such algorithm exists. I will talk about joint work with Alexei Miasnikov and Albert Garreta on decidabilty of the (un)decidabilty of the Diophantine problems in polycyclic groups. I will introduce and describe PE-minimal polycyclic groups (simplest groups that reflect complexity of Diophantine problems in polycyclic groups). Finally I will discuss some open problems about those PE-minimal polycyclic groups and if time allows about generalizations of those ideas to metabelian groups.
Monday Mar 28	Speaker: Mahmood Sohrabi (Stevens) Title: First-order Rigidity of Finitely Generated Rings Abstract: A finitely generated ring is said to be first-order rigid if it can be axiomatized among finitely generated rings by a set of first-order sentences of the language of rings. Such a ring is said to be quasi-finite axiomatizable if a single sentence axiomatizes it among finitely generated rings. In recent years there have been many fascinating developments in this area. In this talk, I will discuss some of these recent developments. In particular, I’ll talk about my joint results with Alexei Myasnikov on first-order rigidity and quasi-finite axiomatizability of finitely generated commutative rings (even without units) and arbitrary rings whose additive groups are finitely generated.
Monday Mar 21	Speaker: Richard Mandel (Stevens) Title: Quadratic equations in unimodular Baumslag-Solitar groups Abstract: For a finitely generated group G, the quadratic Diophantine problem is the problem of deciding whether an equation W(z_1,...,z_k)=1 has a solution in G (where W(z_1,...,z_k) is a word in the generators of G and the unknowns z_i). We will explore the algorithmic complexity of this problem over the unimodular Baumslag-Solitar groups BS(n,+-n), demonstrating NP-completess, and discuss some obstacles in extending the same approach to the general case BS(m,n).
Monday Feb 28	Speaker: Kathrin Smetana (Stevens) Title: Randomized Local Model Order Reduction for Nonlinear Partial Differential Equations Abstract: Applications that require multiple simulation requests or a real-time simulation response and phenomena that exhibit multiscale features are ubiquitous in science and engineering. However, standard discretization methods such as the finite element or finite volume method require an often prohibitively large amount of computational time for such tasks. Approaches developed to tackle these problems comprise multiscale methods that are based on ansatz functions which incorporate the local behavior of the (numerical) solution of the partial differential equation (PDE), model order reduction techniques, in which the problem is (approximately) solved in a carefully chosen subspace of the high-dimensional discretization space, or combinations of multiscale and model order reduction methods. Methods that combine the two approaches are sometimes called localized model order reduction methods. While there has been significant progress in recent years for the construction of local reduced spaces for linear PDE's, very few results have been obtained so far for nonlinear PDE's. In this talk, we will show how randomized methods and their probabilistic numerical analysis can be exploited for the construction and numerical analysis of local reduced models for nonlinear PDE's.

Fall 2021

Monday Nov 22	Speaker: Denis Serbin (Stevens) Title: Which properties of groups can be defined by their pregroup structures? Abstract: In this talk we discuss which properties of pregroups translate into the corresponding properties of their universal groups. First, we are going to give a survey of known results on the subject and then report some new results from the ongoing research on pregroup structures encoding hyperbolicity.
Monday Nov 15	Speaker: Alex Taam (Stevens) Title: Quasi-isometric rigidity of graphs of rigid surface groups. Abstract: A group is a graph of rigid surface groups, or a grsg-group, if it is word hyperbolic and it has a cyclic JSJ decomposition with only rigid type non-cyclic vertex groups, all of which are the fundamental groups of closed surfaces. In this talk, I will discuss recent work with Nicholas Touikan, showing that these groups are quasi-isometrically rigid, in that every quasi-isometry class of grsg-groups consists of a single commensurability class. I will also survey some related results and directions of continuing inquiry.
Monday Nov 8	Speaker: Robert Gilman (Stevens) Title: Is there a better brute force attack? Abstract: It is common in cryptanalysis to assume that the enemy knows everything about your cryptosystem except the decryption key for that day. A brute force attack typically proceeds by trying every possible decryption key on an intercepted encrypted message. It is a simple matter to protect against this attack by choosing the key to be long enough so that the fastest computers available would take, say, ten years to search through all possible keys. In this talk we describe a technique for improving, in theory, some brute force searches; and we speculate on practical applications. This talk is suitable for non-experts and open to all
Monday Nov 1	Speaker: Andrey Nikolaev (Stevens) Title: Some open problems on invariant random subgroups. Abstract: In this talk, I will discuss the notion of parameterized complexity in the context of group theory. The classic Magnus breakdown algorithm that solves the word problem and the word search problem in one-relator groups is well-known to have, generally speaking, non-elementary complexity. I will explain that its parameterized complexity, where the area of a van Kampen diagram serves as a parameter, is polynomial in the length of the input and the parameter. The talk is based on joint work with A. Miasnikov.
Monday Oct 25	Speaker: Simon Thomas (Rutgers) Title: Some open problems on invariant random subgroups Abstract: Let G be a countably infinite group and let Sub_G be the compact space of subgroups H ⩽ G. Then an invariant random subgroup (IRS) of G is a probability measure ν on Sub_G which is invariant under the conjugation action of G on Sub_G. In particular, if ν is ergodic, then ν is a notion of randomness on Sub_G with a 0 -1 law for every group-theoretic property. In this talk, after a brief introduction to the theory of invariant random subgroups, I will discuss some of the many open questions in this relatively new area of group theory.
Monday Oct 18	Speaker: Alexei Miasnikov (Stevens) Title: Esoteric Complexity Abstract: Estimating the efficiency of an algorithm is crucial for computer science. The most important estimate is worst case complexity, i.e., the longest time required by inputs of a given size. However, worst case complexity is not adequate in situations where there are hard instances, but these instances are very rare. In this talk Professor Miasnikov explores some alternatives. This talk is suitable for non-experts.

Spring 2021

Monday May 17	Speaker: Rostislav Grigorchuk (Texas A&M) Title: (Co)Growth, languages and groups generated by subshifts. Abstract: I will begin with a short survey on the use of automata and languages for the study of growth and co-growth in groups. Then I will consider a multivariate version in which frequencies of symbols are prescribed. And finally I will finish with some results concerning groups generated by linear Schreier graphs. Subshifts of finite type and minimal subshifts will be involved in the talk as well.
Monday May 10	Speaker: Robert Gilman (Stevens) Title: Automatic groups: perspectives and open problems Abstract: Automatic groups are finitely generated groups in which the group operation can be described by finite state automata. They were introduced in the 1980's as models for the fundamental groups of compact 3-manifolds although they could equally well have been defined by computer scientists interested in string rewriting. In this talk we will review the history of automatic groups with emphasis on the many open questions concerning them. We will also mention some joint work with Jen Taback on a particular open question posed by Gilbert Baumslag, namely whether or not a one-relator group whose relator is a commutator is necessarily automatic.
Monday May 3	Speaker: Alexei Miasnikov (Stevens) Title: The Diophantine problem in classical matrix groups and algebras Abstract: The Diophantine problem in a group (ring) G is decidable if there exists an algorithm that given a finite system of equations with coefficients in G decides whether or not the system has a solution in G. I will discuss the Diophantine problem in the classical matrix groups G_n(R), where R is an associative unitary ring, n > 2, and G(n,R) is one of the groups GL(n,R), SL(n,R), T(n,R), UT(n,R), PGL(n,R), or PSL(n,R) (in the last two cases we assume that R is also commutative). The main result, loosely stated, is that the Diophantine problems in G(n,R) and R are Ptime reducible to each. In the case when the ring R is finitely generated and commutative the result above allows one to clarify the situation completely, modulo a big conjecture in number theory. For not finitely generated rings, more so for uncountable rings, decidability of the Diophantine problem heavily depends on the set of constants. The case of classical fields of reals, complex and p-adic numbers is especially interesting, as well as the rings of p-adic integers (which is related to pro-p completions of groups). At the end of the talk I will touch on the Diophantine problem in classical associative and Lie matrix algebras, such as Mat(n,R), gl(n,R), sl(n,R). The talk is based on joint results with Mahmood Sohrabi.
Monday Apr 19	Speaker: Denis Ovchinnikov (Stevens) Title: Diophantine problems in rings Abstract: The negative solution to Hilbert's Tenth Problem stating that general polynomial equations are unsolvable over the ring of integers is one of the most famous negative results about an algorithmic problem. Since its publication almost 50 years ago, it has been generalized to many classes of commutative rings. Somewhat amazingly, some of the most natural related questions remain open (for example if we look for rational solutions, or if we look for solutions over some ring of algebraic integers). I will provide a brief introduction on this type of questions, methods that can be used to prove undecidability in different rings, and some new results in that direction. In particular, I will mention finitely generated rings and related cases. I will also discuss a few interesting open problems (that are hopefully not as hard as Hilbert's Tenth Problem for rational).

Fall 2020

Spring 2020

Monday Apr 6	Speaker: Johanna Franklin (Hofstra) Title: Lowness in computable structure theory Abstract: Computability theory has many notions of lowness. In general, we say a Turing degree is low in some situation if it doesn't give any useful information when it's used as an oracle there. I'll talk about degrees that are low for isomorphism: degrees that can only compute an isomorphism between two computably presented structures when there is already a computable isomorphism between them. I'll focus on the types of closure properties this class of degrees has and then talk a little about the ways in which this class is related to other, commonly studied classes of degrees.
Monday Mar 2	Speaker: Denis Ovchinnikov Title: Decidability of the Diophantine Problem in rings and groups. Abstract: The famous Hilbert’s Tenth problem asked whether there is an algorithm to solve equations over integers. The negative answer (the Matiyasevich-Robinson-Davis-Putnam Theorem) is one of the most interesting results regarding decidability of algorithmic problems in algebra. In general, given an algebraic structure (for example ring or a group), one can ask whether there is an algorithm to decide if a system of equations over that structure has a solution or not (that is whether the Diophantine Problem is decidable or not). This has been a rich area of research regarding both decidable Diophantine Problems (Makanin-Razborov algorithm) and undecidable Diophantine Problems (various rings and some groups). I will present new results on the undecidability of this problem in some groups and rings. With the use of bilenear maps it is possible to reduce the Diophantine Problem over nilpotent groups to the Diophantine Problem over algebraic integers. We then use nilpotent groups to reduce the Diophantine Problem over a large class of groups (for example many metabilan and solvable groups, matrix groups) to the Diophantine problem over a ring of algebraic integers. We deduce undecidability of Diophantine Problem in some of these groups (when the resulting ring is the ring of rational integers), and conjecture the undecidability in general (undecidability of Diophantine Problem in rings of algebraic integers is a major open problem).
Monday Feb 24	Speaker: Sam Corson Title: A weird almost free group Abstract: Almost free groups (groups whose subgroups of smaller cardinality are free) have been a subject of study over the last 60 years. Some such groups can be made to satisfy further conditions which are satisfied by free groups, while still failing to be free. Principles of combinatorial set theory generally play a role in such constructions. I’ll give a review of almost free groups, including history and some examples, and present a recent result.

Fall 2019

Monday	Speaker: Jan Cannizzo (Stevens) Title: Surjunctive groups Abstract: A finitely generated group G is said to be surjunctive if any cellular automaton over G that is injective is surjective as well. This talk will give a brief overview of surjunctive groups and introduce some techniques intended to address the question "Which groups are surjunctive?".
Monday Nov 11	Speaker: Marco Avella-Medina (Columbia University) Title: Privacy-preserving parametric inference: a case for robust statistics Abstract: Differential privacy is a cryptographically-motivated definition of privacy that has become a very active field of research over the last decade in theoretical computer science and machine learning. In this paradigm we assume there is a trusted curator who holds the data of individuals in a database and the goal of privacy is to simultaneously protect individual data while allowing statistical analysis of the database as a whole. In this setting we introduce a general framework for parametric inference with differential privacy guarantees. We first obtain differentially private estimators based on bounded influence M-estimators by leveraging their gross error sensitivity in the calibration of a noise term added to them in order to ensure privacy. We then we show how a similar construction can also be applied to construct differentially private test statistics analogous to the Wald, score and likelihood ratio tests. We provide statistical guarantees for all our proposals via an asymptotic analysis. An interesting consequence of our results is to further clarify the connection between differential privacy and robust statistics. In particular we demonstrate that differential privacy is a weaker requirement than infinitesimal robustness and show that robust M-estimators can be easily randomized in order to guarantee both differential privacy and robustness towards the presence of contaminated data. We illustrate our results both on simulated and real data.
Monday Nov 4	Speaker: Russell Miller, (Queens College, CUNY) Title: Uniform Computable Categoricity for Fields Russell Miller, (Queens College, CUNY) Abstract: Computability theorists have learned not to take isomorphism for granted. It is quite possible for two computable structures (i.e., structures with decidable atomic diagrams) to be isomorphic to each other, yet for there to be no isomorphism between them that can be computed (as a function from one domain onto the other). This is important because, if the structures fail to be computably isomorphic, then one of them may have very nice computability-theoretic properties, while the other does not, despite being (non-computably) isomorphic to the first. For example, two computable fields can be isomorphic, but if they are not computably isomorphic, then in one it may be undecidable which field elements have square roots, while in the other the same question may be decidable. Computable categoricity of a structure means that these pathologies cannot happen: for every pair of computable copies of the structure, there is a computable isomorphism between them. Fields were the first class of structures for which computable categoricity was studied, by Fr\"ohlich and Shepherdson in the 1950's. We will discuss a uniform version of computable categoricity for fields, which will be accessiblewith no background at all beyond a very basic knowledge of field theory. Even so, we will be able to understand several recent results, some by the speaker and (time permitting)some joint with Hans Schoutens.
Monday Oct 28	Speaker: Lubjana Beshaj (USMA, West Point) Title: Isogenous components of Jacobian surfaces Abstract: Increased computational power, such as offered by quantum computers, poses a threat to both public key cryptography and digital signature algorithms. In order to mitigate this imminent threat, cryptographic schemes that are resistant against quantum computers have drawn great attention from academia, governments and industry. These schemes are collectively referred to as post-quantum cryptography (PQC). There are several candidates for new public-key encryption, key establishment algorithms and digital signature algorithms. These candidates include code based cryptography, multivariate cryptography, lattice-based cryptography, hash-based cryptography, and supersingular isogeny-based cryptography. In 2011 Jao and DeFeo proposed Supersingular Isogeny Diffie- Hellman (SIDH) as a key exchange protocol. Isogeny based algorithms rely on the structure of large isogeny graphs and the cryptographically interesting properties of these graphs are tied to their expansion properties. In this talk we will cover the mathematical background needed for supersingular isogeny based cryptography and some current research on isogenous components of 2-dimensional reducible Jacobians.
Monday Oct 21	Speaker: Mahmood Sorabi (Stevens) Title: Groups elementarily equivalent to SL_n(O), GL_n(O), and T_n(O), n>2. Abstract: In this talk we study bi-interpretability of the structures in question with the ring of integers Z, and in each case we provide a characterization for groups elementarily equivalent to the group. This is joint work with Alexei Miasnikov.
Monday Oct 7	Speaker: Alexei Miasnikov (Stevens) Title: Parametric complexity and group theory Abstract: Parameterized complexity is a recent but active area of modern computer science. I will show how parameterized complexity arises naturally in algorithmic and geometric group theory and will describe some initial results and interesting open problems.
Monday Sept 23	Speaker: Gretchen Ostheimer (Hofstra) Title: A look at circuit complexity and group theory Abstract: In 2018 Alexei Miasnikov and Armin Weiss proved that a host of the classical problems concerning finitely generated nilpotent groups lie in a circuit complexity class known as TC^0. This talk is intended as an introduction to this area of research. We will try to get a feel for TC^0 by looking at one of their results from a slightly different perspective. My hope is to generate some interest in the problems left open by their work.
Monday Sept 16	Speaker: Artem Chernikov (UCLA) Title: Regularity lemma for hypergraphs with forbidden patterns Abstract: Fix an arbitrary bipartite finite graph H, and let's consider the family of all finite graphs not containing H as an induced subgraph. Recently a strong form of Szemeredi's regularity lemma for such families was established by Lovasz and Szegedy. In particular, up to an arbitrary small error, such graphs can be uniformly approximated by direct products of unary relations. Using a combination of analytic, combinatorial and model-theoretic methods, we establish a generalization of this result for hypergraphs, showing that k-ary hypergraphs omitting a fixed k-partite hypergraph H can be uniformly approximated by relations of arity smaller than k. No prior knowledge of the aforementioned notions will be assumed. Joint work with Henry Towsner.

Spring 2019

Monday Apr 29	Speaker: Sasha Ushakov (Stevens) Title: The Conjugacy Problem in the Grigorchuk group Abstract: We show that the Conjugacy Problem in the Grigorchuk group can be solved in linear time.
Monday Apr 22	Speaker: Denis Serbin (Stevens) Title: How to fellow-travel in graph automatic groups Abstract: In ongoing joint work with Andrey Nikolaev we propose an analog of the k-fellow traveler property from the theory of automatic groups, for graph automatic groups. Some applications will also be discussed.
Monday Apr 15	Speaker: Vladimir Shpilrain (CUNY) Title: Unconditionally secure public key transport (with possible errors) Abstract: We consider a scenario where one party wants to transmit a secret key to another party in the presence of a computationally unbounded (passive) adversary. The legitimate parties succeed with probability close to 1 (although strictly less than 1), while a computationally unbounded passive adversary succeeds in correctly recovering the secret key with significantly lower probability. This is joint work with Mariya Bessonov and Dima Grigoriev.
Monday Apr 1	Speaker: Antonio Nicolosi (Stevens) Title: A Step or Two with Burnside Groups of Exponent Three Abstract: This will be an informal talk reporting on some of our work on designing and implementing a cryptographic library based on Burnside groups of exponent three. In particular, we will describe some optimization techniques to speed up both the group operation and the calculation at the core of our encryption algorithm. Based on recent research with Justin Barish (Stevens BS+MS '19), and earlier work with Nelly Fazio (CCNY) and Linda Wong (CCNY BS'12).
Monday Mar 25	Speaker: Stefan Wüller (Stevens) Title: Towards Privacy-Preserving Electronic Bartering Abstract: Bartering is defined as the cashless act of trading goods and services in exchange for other goods and services. Both B2B bartering as well as bartering between individuals is increasingly facilitated through online platforms. An inherent requirement of these platforms is that a user has to disclose its trading capabilities to the operator and typically also to all other users. As a consequence, private information on the personal preferences of a user is leaked which can undermine his bargaining position. In this talk I will present a cryptographic protocol for determining an actual trade between multiple users in a privacy-preserving fashion without involving a (trusted) third party.
Monday Feb 25	Speaker: Albert Garreta Fontelles (Universidad del País Vasco / Euskal Herriko Unibertsitatea) Title: Equations in some hyperbolic and one-relator monoids Abstract: I will introduce and survey the problem of solving word equations with length constraints, a long-standing open problem in computer science whose decidability or undecidability has interesting consequences. I will then explain how this problem can be reduced to the Diophantine problem of some word-hyperbolic (in several senses) monoids and one-relator monoids, establishing some comparisons with their group-theoretic counterparts along the way. This is joint work with Robert Gray.
Monday, Jan 28	Speaker: Jennifer Taback (Bowdoin) Title: How close can a graph automatic group come to being automatic? Abstract: Given a Cayley graph automatic group G with a particular graph automatic structure, Berdinsky and Trakuldit define a function to measure how close that structure is to being automatic. In ongoing joint work with Murray Elder, we refine and explore this idea, linking it to finite presentability and the Dehn function of the group. This is an informal talk.

Fall 2018

Monday, Sep 24

Speaker: Martin Kreuzer, University of Passau
Title: Refuting Products of Linear Polynomials

Abstract: In this talk, which is based on joint work with Jan Horacek (Passau), we introduce and study a new proof system for refuting products of linear polynomials, or, equivalently, sets of linear clauses. This proof system combines the power of the resolution rule in propositional logic with the construction of S-polynomials and polynomial reduction in the polynomial calculus.

The caveat is that is works only for special sets of clauses resp. special polynomials. However, these are exactly the types of clauses resp. polynomials that we encouter when we perform algebraic attacks or algebraic fault attacks in cryptography. A preliminary implementation of the new proof system shows already good behaviour for certain types of fomulas (such as Tseitin formulas) which are notoriously difficult to treat using SAT solvers.

Spring 2018

Monday, Feb 5	Speaker: Alexander Ushakov (Stevens) Title: "Simultaneous conjugacy separation search problem: attack on Algebraic Eraser" Abstract: I will discuss Algebraic Eraser key-agreement protocol proposed in the paper I. Anshel, M. Anshel, D. Goldfeld, and S. Lemieux. Key agreement, the algebraic eraser, and lightweight cryptography. In Algebraic Methods in Cryptography, volume 418 of Contemporary Mathematics, pages 1--34. American Mathematical Society, 2006. I will define Algebraic Eraser, discuss history of attacks and present a new attack that has 100% success on VERY LONG keys.
Monday, Feb 12	Speaker: Johanna Franklin (Hofstra) Title: "Algorithmically random points" Abstract: I will use computability theory to characterize randomness in the Cantor space using three different intuitive approaches: unpredictability, incompressibility, and a lack of distinguishing properties. After developing this basic framework, I will present different formalizations that result in different classes of random points and discuss the relationships between these classes and naturally occurring classes in other areas of mathematics.
Monday, Feb 24	Speaker: Igor Lysenok (Stevens and the Russian Academy of Sciences , Moscow · Steklov Mathematical Institute) Title: "Small cancellation theory and Burnside groups" Abstract: This is brief overview of iterated small cancellation theory that can be applied to Burnside groups of odd exponents n with moderate bound n > 2000.
Monday, Mar 5	Speaker: Rizos Sklinos (Stevens) Title: "Forking in the free group" Abstract: The first-order theory of nonabelian free groups attracted much attention when Kharlampovich-Miasnikov and Sela answered in the positive Tarski's question on whether nonabelian free groups share the same common first-order theory. In addition, Sela proved the astonishing result that this common first-order theory is stable, making it possibly the most interesting example of a stable group. Roughly speaking, a first order theory is stable when one can find a "nice" independence relation in all of its models. Prototypical examples being linear independence in vector spaces and algebraic independence in algebraically closed fields. Stability had been discovered by Shelah in his famous and successful classification program where he classified first-order theories according to the number of non-isomorphic models they have in every cardinality. In joint work with C. Perin we give a natural geometric interpretation of this independence relation in nonabelian free groups.
Monday, Mar 19	Speaker: Alexander Ushakov (Stevens) Title: "The Kayawood protocol" Abstract: Kayawood is a two party Diffie-Hellman type protocol recently proposed by Iris Anshel, Derek Atkins, Dorian Goldfeld, and Paul E. Gunnells. The paper is available here: https://eprint.iacr.org/2017/1162 In my talk I will define the protocol, discuss its security features, and show how to reduce a passive attack challenge to a certain search problem over braid groups.
Monday, Mar 26	Speaker: Alexander Ushakov (Stevens) Title: "Walnut DSA" Abstract: The next in a series of talks on cryptanalysis. Walnut DSA is a new digital signature algorithm proposed by SecureRF that uses action of braids on a finite set (aka e-multiplication). See https://eprint.iacr.org/2017/058.pdf .
Monday, Apr 2	Speaker: Yuri Gurevich (University of Michigan) Title: "What's quantum computing anyway?" Abstract: Using the example of the function inversion problem, we illustrate the power and limitations of quantum computing. No knowledge of quantum computing is assumed..
Monday, Apr 16	Speaker: Alexei Miasnikov (Stevens) Title: "First Order Paradise" Abstract: A long time ago Malcev asked about definable subgroups in free groups. It turned out that the obvious ones are the only definable subgroups there. A similar question can be asked about any group, or semigroup, or ring. I am interested in groups where all reasonable subgroups are first-order definable. In fact, are there such “non-trivial and interesting” groups or rings? Surprisingly, the answer is YES. I will talk about classical algebraic structures (groups, rings, and such) where "anything you reasonably want" is first-order definable. I will explain what does this mean precisely and show some results.
Monday, Apr 23	Speaker: Alexei Miasnikov (Stevens) Title: "First Order Paradise (continued)"
Monday, May 7	Speaker: Alexei Miasnikov (Stevens) Title: "Algorithmic Group Theory and Cryptography"
Monday, May 13	Speaker: Anand Pillay, University of Notre Dame Title: "Pseudofinite groups and combinatorics" Abstract: I will discuss some joint work with Gabriel Conant and Caroline Terry. This concerns Szemeredi-type theorems in the contexts of finite groups G equipped with a distinguished subset A. Under various conditions on the relation x∙y ∈ A we give asymptotic descriptions of A and its translates in G. The methods involve local stability and local NIP theorems for pseudofinite groups. I will discuss some joint work with Gabriel Conant and Caroline Terry. This concerns Szemeredi-type theorems in the contexts of finite groups G equipped with a distinguished subset A. Under various conditions on the relation x∙y ∈ A we give asymptotic descriptions of A and its translates in G. The methods involve local stability and local NIP theorems for pseudofinite groups.

Fall 2017

Monday, Sept 18	Speaker: Alexei Mishchenko (Sobolev Institute of Mathematics) Title: " Canonical and existentially closed groups in universal classes of abelian groups"
Monday, Sept 25	Speaker: Sasha Treyer (Stevens) Title: "The knapsack problem for nilpotent groups and Baumslag-Solitar groups"
Monday, Oct 2	Speaker: Florian Walsh (University of Passau) Title: "Computation of Idempotents in Rings using Primary Decomposition"
Monday, Oct 16	Speaker: Igor Lysenok ( Stevens and the Russian Academy of Sciences , Moscow · Steklov Mathematical Institute) Title: "The Commutator width of the Grigorchuk group"
Monday, Oct 30	ACC Organizational Meeting
Monday, Nov 6	Speaker: Alina Vdovina (Newcastle University and Hunter College) Title: *"Buildings and K-theory of C-algebras" Abstract:** Explicit constructions of C-algebras and computing their K-theory are believed to be useful for quantum computing. We will give constructions of C- algebras using Ballmann-Brin geometric approach to buildings and polygonal presentations introduced by the speaker in early 2000s. It gives very explicit combinatorial ways to compute the K-theory of our C*-algebras which can not be achieved by the standard methods of Operator theory.
Monday, Nov 13	Speaker: Olga Kharlampovich (Hunter College, CUNY) Title: "Random Burnside groups" Abstract: I will discuss Gromov-Delzant-Coulon construction of infinite Burnside groups and different models of random Burnside groups.
Monday, Nov 20	Speaker: Vladimir Shpilrain (City College, CUNY) Title: "Fully homomorphic encryption on rings"
Monday, Dec 4	Speaker: Rizos Sklinos (Stevens) Title: "Some model theory of nonabelian free groups" Abstract: Around 1946 Tarski asked whether nonabelian free groups share the same common theory. Many mathematicians, Mal’cev, Lyndon, Makanin to name a few, have approached the problem and contributed to it. Despite their efforts the problem seemed very hard to tackle and only after more than fifty years, in 2001, a positive answer was given by Kharlampovich-Myasnikov and Sela independently. Since then, the common theory of nonabelian free groups has attracted a lot of attention from the community of model theorists and group theorists. The positive solution to Tarski’s question is considered one of the deepest results in the model theory of groups. In this talk I am going to survey the results that are currently known about this first-order theory and pose problems that are still open.

Fall 2016

Monday, Oct 24	Speaker: Jan Cannizzo (Stevens) Title: "New trends in education"
Monday, Nov 7	Speaker: Michael Shapiro (Tufts University) Title: "Generalized Dehn's algorithms" Abstract: Early last century, Dehn articulated the three problems which we now call the word problem, the conjugacy problem and the isomorphism problem. He then solved the word problem for surface groups. For example, consider G = ⟨x₁, y₁, x₂, y₂ \| ℜ := [x₁, y₁][x₂, y₂] = 1⟩ Dehn observes that any non-trivial word for the identity contains more than half of a cyclic permutation of ℜ or ℜ^-1. This gives a finite set of length-decreasing substitutions which produces the empty word if and only if the original word is the identity. We call such a set of relations a Dehn's algorithm. Cannon showed that any group acting co-compactly, discretely by isometries on Hⁿ has a Dehn's algorithm. Indeed, a group is hyperbolic if and only if it has a Dehn's algorithm. What happens if we are allowed to make substitutions using letters which are not elements of the group? In joint work with Oliver Goodman, inspired by Cannon, we show that this new class of groups includes finitely generated nilpotent groups and relatively hyperbolic groups with nilpotent peripheral sub- groups. We can also show that some groups (for example solve geometry, F × Z, Thomsen's groups) do not have generalized Dehn's algorithms.
Monday, Nov 14	Speaker: Consuelo Martinez Lopez (Universidad de Oviedo) Title: "Ellipticity of Words in Groups and Algebras" Abstract: In this talk we will deal with words w of the free pro-p-group F and we will try to show classes of groups in which every such word w is elliptic. Keeping in mind the linearization process in algebras, we will define a notion of multilinear word w in F and we will show some stronger result for the case of multilinear words. We will consider also the notion of ellipticity in Lie algebras.
Monday, Nov 21	Speaker: Alexey Ovchinnikov (Queens College, CUNY) Title: "Bounds in algebraic differential equations" Abstract: Differential Nullstellensatz is a fundamental fact in the algebraic theory of differential equations. It states that, if a system of algebraic differential equations does not have a solution in any extension of the coefficient field, then 1 can be written as a polynomial linear combination of the derivatives of the equations of the original system up to some order. Thus, due to the classical effective polynomial Nullstellensatz, finding bounds for this order is a key ingredient in understanding the complexity of the problem. We will present a new and improved bound for the effective version of the differential Nulstellensatz. Our approach is based on using triangular sets in the prolongation-projection method.
Monday, Nov 28	Speaker: Sam Van Gool (The City College, CUNY) Title: "Pro-aperiodic monoids via saturated models" Abstract: The class of aperiodic monoids has long played a fundamental role in finite semigroup theory and automata theory. In this work we apply Stone duality and model theory to study the structure theory of free pro-aperiodic monoids. Stone duality implies that elements of the free pro-aperiodic monoid may be viewed as elementary equivalence classes of pseudofinite words. Model theory provides us with saturated words in each such class, i.e., words in which all possible factorizations are realized. We give several applications of this new approach. This talk is on joint work with Ben Steinberg (CCNY), see our preprint here.

Spring 2016

Monday, Feb 8	Speaker: Alexander Ushakov (Stevens) Title: "The quantum Fourier transform"
Monday, Feb 22	Speaker: Igor Lysenok (Stevens) Title: "Solving quadratic equations in metablelian groups"
Monday, Feb 29	Speaker: Dmitry Panteleev (Stevens) Title: "The conjugacy search problem and the Andrews-Curtis conjecture"
Monday, Mar 14	Speaker: Nicholas Touikan (Stevens) Title: "Report on Young Geometric Group Theorists V"
Monday, Mar 28	Speaker: Khalid Bou-Rabee (The City College, CUNY) Title: "Intersection growths of groups" Abstract: Intersection growth concerns the asymptotic behavior of the index of the intersection of all subgroups of a group that have index at most n. We motivate studying this growth and explore some examples with a focus on nilpotent groups and zeta functions. This covers joint work with Ian Biringer, Martin Kassabov, and Francesco Matucci.
Monday, Apr 4	Speaker: Eric Allender (Rutgers University) Title: "Zero Knowledge and Circuit Minimization" Abstract: For roughly four decades, two of the best-studied problems in NP that are not known to be in P or to be NP complete have been: * Graph Isomorphism, and * MCSP (the Minimum Circuit Size Problem). Yet there had been no theorem, relating the complexity of these two problems to each other. Until recently. We give a simple argument - drawing on the connection between MCSP and time-bounded Kolmogorov complexity - showing that not only Graph Isomorphism, but every problem in the complexity class SZK (Statistical Zero Knowledge) is BPP reducible to MCSP (joint work with Bireswar Das). If there is time, I'll also discuss more recent work on a related topic (joint with Josh Grochow and Cris Moore).
Monday, Apr 11	Speaker: Doron Puder (Institute for Advanced Study) Title: "Word Measures on Unitary Groups" Abstract: This is joint work with Michael Magee. We combine concepts from random matrix theory and free probability together with ideas from geometric group theory, and establish new connections between the two. More particularly, we study measures induced by free words on the unitary groups U(n). For example, if w is a word in F₂ = ⟨x,y⟩, sample at random two elements from U(n), A for x and B for y, and evaluate w(A,B). The measure of this random element is called the w-measure on U(n). We study the expected trace (and other statistics) of a random unitary matrix sampled from U(n) according to the w-measure, and find surprising algebraic properties of w that determine these quantities. If time permits, I will also describe one of the main ingredients from the proof: a finite simplicial complex which is an Eilenberg-MacLane space for certain subgroups of the mapping class group of a compact surface with boundary.
Monday, May 2	Speaker: Nikolay Romanovskiy (Sobolev Institute of Mathematics, Siberian Branch of Russian Academy of Sciences, Novosibirsk, Russia) Title: "Splittings of groups over abelian normal subgroups" Abstract: Let A be an abelian normal subgroup of a group G. Let G = G / A, g = gA for g ∈ G. We can consider A as a right ZG-module, by defining an action of u = α₁ g₁ + … + α_n g_n ∈ ZG on a ∈ A as a^u = (a^g₁)^α₁ ⋅ … ⋅ (a^g_n)^α_n, where (a^g_i)^α_i = g_i^-1 a g_i. Denote by Θ_ZG(A) the annihilator of A in the group ring ZG, and put R = ZG / Θ_ZG(A). A is also an R-module. We study when there is an R-splitting of G over A.
Monday, May 9	Speaker: Alexander Treyer (Sobolev Institute of Mathematics, Siberian Branch of Russian Academy of Sciences, Omsk, Russia) Title: "Subset sum problem in wreath products of groups" Abstract: It will be shown that SSP is strongly NP-complete for Lampligher group. This result will be extended to more general cases of wreath products.

Fall 2015

Monday, Sep 27	Speaker: Nicholas Touikan (Stevens) Title: "Finding surface subgroups in graphs of free groups: looking back on 5 years of failure." Abstract: I will report on my work in progress with Inna Bumagin on the construction of Makanin-Razborov diagrams for relatively hyperbolic groups with possibly non-abelian parabolics and possibly with torsion. The approach is a generalization of previous methods. I hope to touch upon some of the innovations in (delta-hyperbolic metric) geometry, as well as in algebraic geometry needed to get the claimed result.
Monday, Oct 19	Speaker: Igor Lysenok (Stevens) Title: "A discrete curvature approach to finitely presented groups" Abstract: We consider a sufficient condition on a finite presentation of a group which guarantees its hyperbolicity. The condition is formulated in terms of negative value of a certain discrete analog of curvature of Lyndon-van Kampen diagrams over the presentation. There are examples of computer implemented proof of hyperbolicity of some finitely presented groups though no general algorithm has been elaborated.
Monday, Oct 26	Speaker: Yuri Gurevich (Microsoft Research) Title: "Logic in computer science and software enginering" Abstract: Eugene P. Wigner and Richard W. Hamming wrote about the “unreasonable effectiveness” of mathematics in the natural sciences. This inspired Joseph Y. Halpern, Robert Harper, Neil Immerman, Phokion G. Kolaitis, Moshe Y. Vardi, and Victor Vianu to write about the “unusual effectiveness” of logic in computer science. Moshe Vardi gives talks about a “logic revolution” in computer science and, to an extent, software engineering. We are a bit less jubilant about the role that logic and logicians have been playing in science and engineering. Logic had the greatest prestige in the ﬁrst part of the 20th century. Today, its role could be - and should be - bigger, especially in software engineering. Software engineers studied calculus but rarely, if ever, use it. They did not study formal logic but use day in and day out, even though many of them do not realize that. We will try to illustrate why formal logic is so relevant for software engineers, and why it is hard for them to pick it up.
Monday, Nov 2	Speaker: Gretchen Ostheimer (Hofstra University) Title: "Decomposability of finitely generated torsion-free nilpotent groups" Abstract: We describe an algorithm for deciding whether or not a given finitely generated torsion-free nilpotent group is decomposable as the direct product of nontrivial subgroups. This is joint work with Gilbert Baumslag and Chuck Miller.
Monday, Nov 16	Speaker: Armin Weiß (Universität Stuttgart, Stuttgart, Germany) Title: "QuickMergesort: Efficient Sorting with n log n - 1.399n + o(n) Comparisons on Average" Abstract: Sorting a sequence of elements of some totally ordered universe is one of the most frequent tasks carried out by computers. Classical algorithms for this problem are Quicksort, Heapsort, or Mergesort. In 2000, Cantone and Cincotti described QuickHeapsort -- a hybrid algorithm combining of Quicksort and Heapsort. We generalize the idea of QuickHeapsort leading to the notion of QuickXsort. Given some sorting algorithm X which uses external memory, QuickXsort yields an internal sorting algorithm if X satisfies certain natural conditions. With QuickWeakHeapsort and QuickMergesort we present two examples for the QuickXsort-construction. Both are efficient algorithms that incur approximately n log n - 1.26n + o(n) comparisons on the average. A worst case of n log n + O(n) comparisons can be achieved without significantly affecting the average case. QuickMergesort shows a good performance on practical inputs: when sorting integers it is slower by only 15% to STL-Introsort. Moreover, by sorting small sub-arrays with MergeInsertion, we establish a worst-case efficient internal sorting algorithm calling for n log n - 1.399n+o(n) comparisons on average - thus, coming close to the information theoretic lower bound.
Monday, Nov 30	Speaker: Michael Zabarankin (Stevens) Title: "Support vector machines"

Spring 2015

Tuesday, Feb 3	Speaker: Johannes A. Buchmann (Technische Universität Darmstadt, Germany) Title: "Post-Quantum-Cryptography - an overview" Abstract: In this talk we explain the idea and relevance of public-key cryptography. We explain that quantum computers will be able to break all public-key cryptography that is used today. We will give an overview over the most promising approaches to come up with quantum-safe public-key cryptography.
Tuesday, Mar 10	Speaker: Olga Kharlampovich (Hunter College, CUNY) Title: "Elementary classification questions for algebras and group rings" Abstract: We consider some fundamental model-theoretic questions that can be asked about a given algebraic structure (a group, a ring, etc.), or a class of structures, to understand its principal algebraic and logical properties. These Tarski type questions include: elementary classification and decidability of the first-order theory. In the case of free groups we proved that two non-abelian free groups of different ranks are elementarily equivalent, classified finitely generated groups elementarily equivalent to a finitely generated free group (also done by Sela) and proved decidability of the first-order theory. We describe partial solutions to Tarski's problems in the class of free associative, free Lie algebras of finite rank and group algebras, and some open problems. In particular, we will show that unlike free groups, two free associative algebras of finite rank over the same field are elementarily equivalent if and only if they are isomorphic. Two free associative algebras of finite rank over different infinite fields are elementarily equivalent if and only if the fields are equivalent in the weak second order logic, and the ranks are the same. We will also show that for an infinite field the theory of a free associative algebra is undecidable. These are joint results with A. Miasnikov.
Tuesday, Mar 31	Speaker: Nikolay Romanovskiy (Sobolev Institute of Mathematics, Siberian Branch of Russian Academy of Sciences, Novosibirsk, Russia) Title: "Q-completions of free solvable groups"
Tuesday, Apr 14	Speaker: Simon Smith (New York City College of Technology, CUNY) Title: "Totally disconnected locally compact groups and groups acting on locally finite graphs" Abstract: The study of locally compact groups divides naturally into investigating those which are connected, and those which are totally disconnected. Since the solution of Hilbert's Fifth Problem, connected locally compact groups are known to be projective limits of connected Lie groups, and because of this their structure is now relatively well-understood. On the other hand, the class of totally disconnected locally compact (tdlc) groups contains all discrete groups (and therefore all groups) and so it was thought that very little in general could be said about their structure. This changed in 1994 when George Willis proved that tdlc groups admit a scale function. The scale function on a tdlc group G measures the translation length of elements in G acting by conjugation on the set of compact open subgroups of G. Roggi Moller recovered Willis' work by looking only at groups acting on locally finite graphs, and it is this approach that I will describe in my talk. Thinking about tdlc groups in terms of groups acting on locally finite graphs is a natural way for those who work primarily with finitely generated groups to begin thinking about the theory of tdlc groups. This new way of looking at tdlc groups offers insight into their structure, and has led to the solution of a number of open problems, one of which I will talk about in detail.
Tuesday, Apr 21	Speaker: Nelly Fazio (The City College, CUNY) Title: "TBA"
Tuesday, Apr 28	Speaker: Eugene Plotkin (Bar Ilan University, Israel) Title: "Similarity of geometries over algebras" Abstract: We will discuss thoroughly how to define closeness of geometries over algebras of the same variety. We will show that there is a kind of rigidity theorem for a number of varieties. All the necessary notions will be defined.

Fall 2014

Monday, Sep 22	Speaker: Alexei Miasnikov (Stevens) Title: "Tarski problems in free groups"
Monday, Sep 22	Speaker: Bob Gilman (Stevens) Title: "On the Andrews-Curtis Conjecture"
Monday, Oct 5	Speaker: Nicholas Touikan (Stevens) Title: "Makanin-Razborov diagrams for relatively hyperbolic groups" Abstract: I will report on my work in progress with Inna Bumagin on the construction of Makanin-Razborov diagrams for relatively hyperbolic groups with possibly non-abelian parabolics and possibly with torsion. The approach is a generalization of previous methods. I hope to touch upon some of the innovations in (delta-hyperbolic metric) geometry, as well as in algebraic geometry needed to get the claimed result.
Tuesday, Oct 14	Speaker: Artem Shevlyakov (Omsk State University) Title: "Semigroups with inversion: equations and algebraic sets" Abstract: I consider equations over inverse, completely simple and completely regular semigroups. The disjunction of two solution sets of an equation is not necessarily equal to a solution set of an appropriate system of equations. We describe the semigroups from the classes above, where ANY disjunction of the solution sets is algebraic (i.e. it equals to a solution set of some system of equations).
Monday, Oct 20	Speaker: Antonio Nicolosi (Stevens) Title: "Hard learning problems over non-commutative groups"
Monday, Oct 27	Speaker: Artem Shevlyakov (Omsk State University) Title: "Equations and logical classes of left regular bands" Abstract: The semigroup class of left regular bands (LRB) is defined by the identities xx=x, xyx=xy, and it has many applications in mathematics. Precisely, such semigroups are used in matroid theory, random walks and hyperplane arrangements. The general motivation of my study was a logical classification of matroids. Namely, I tried to understand the matroids which are close to the free matroid using LRB-s. This problem compelled me to develop algebraic geometry over LRB-s. In this talk I give a classification of LRB-s relative to their equational properties.
Monday, Nov 3	No seminar
Monday, Nov 10	Speaker: Xiaohu Li (Stevens) Title: "Algebraic statistics" Speaker: Alexei Mishchenko and Sasha Treyer (Omsk State University) Title: "Generic theories of abelian groups"
Monday, Nov 17	Speaker: Ben Steinberg (The City College, CUNY) Title: "A universal syntactic invariant of flow equivalence of symbolic dynamical systems" Abstract: A symbolic dynamical system (or shift space) is a shift-invariant closed subspace of a Cantor space A^Z. Flow equivalence is a classical coarsening of the notion of conjugacy (or isomorphism). Since A^Z is the space of all bi-infinite words over the alphabet A, shift spaces are determined by their languages of finite factors, and flow equivalence can be described syntactically in terms of sliding block codes and symbol expansions, it is natural to try to derive syntactic invariants of flow equivalence from their associated languages. In this talk we introduce a new syntactic invariant, called the Karoubi envelope, of a symbolic dynamical system. We indicate how under mild hypotheses it classifies the Markov-Dyck and Markov-Motzkin shifts associated to graphs by W. Krieger. It turns out to be a finer invariant than essentially all syntactic invariants that we are aware of in the literature (including some that were only known to be conjugacy invariants). We also have that the Karoubi envelope is a universal syntactic invariant for sofic shifts in the sense that any flow equivalence invariant for sofic shifts that agrees on all sofic shifts with isomorphic syntactic semigroups automatically agrees on all shifts with equivalent Karoubi envelopes. I will not assume for this talk the audience has any prior contact with symbolic dynamic. All notions will be introduced from scratch and worked with combinatorially. I hope the talk will be accessible to graduate students. This is a report on joint work with Alfredo Costa (Coimbra).
Monday, Nov 24	Speaker: Jan Cannizzo (Stevens) Title: "Invariant random subgroups: background, results, and open problems" Abstract: I'll give an introduction to the theory of invariant random subgroups, which has recently attracted a lot of attention. I'll aim to survey a number of results, including my own work (some of which is joint with Vadim Kaimanovich), and indicate open problems and new directions.
Monday, Dec 1	Speaker: Funda Gul (Stevens) Title: "Some algorithmic properties of Magnus embedding and generalization of Auslander-Lyndon theorem"



	Stevens Institute of Technology • Hoboken, NJ • (201) 216-5000 Sitemap