2:30-3:30 pm

Room 3307, CUNY Graduate Center

365 Fifth Avenue at 34th Street

**February 5:** Alexander A. Mikhalev (Moscow State University), *Cryptographic algorithms on groups and algebras*
**Abstract: ** We analyze algorithms for public key exchange on some
noncommutative groups. Algorithms for factorization and decomposition in associative
algebras (of small dimension) are considered, too.
We also give a survey of applications (in particular, to cryptography) of the
so-called ``hidden matrices''.

This talk is based on a joint work with A. S. Kuzmin, V. T. Markov,
A.V. Mikhalev, and A. A. Nechaev.

**February 19:** Bianca Sosnovski (Queensborough Community College and CUNY Graduate Center), *Cayley graphs of semigroups and applications to hashing*
**Abstract: ** Tillich and Zemor proposed a scheme for a family of hash functions (1994), which uses products of matrices in groups of the form SL_2(F_{2^n}). In 2009, Grassl et al. developed an attack to obtain collisions for palindromic bit strings by exploring a connection between the Tillich-Zemor functions and maximal length chains in the Euclidean algorithm for polynomials over F_2. We propose a new platform to be used in the Tillich-Zemor scheme (1994). The platform consists of the (semi)group of linear functions in one variable over F_p under composition generated by f(x)=2x+1 and g(x)=3x+1. The corresponding hash functions are efficient and a lower bound is provided on the minimum length of bit strings where a collision may occur.

Based on joint work with Vladimir Shpilrain.

**February 26:** Tullia Dymarz (University of Wisconsin-Madison), *Nonrectifiable Delone sets in amenable groups*
**Abstract: ** In 1998 Burago-Kleiner and McMullen constructed the first examples of coarsely dense and uniformly discrete subsets of R^n that are not bi-Lipschitz equivalent to the standard lattice Z^n for n \geq 2. We will show how to find such sets inside certain other solvable Lie groups. The techniques involve combining ideas from Burago-Kleiner with quasi-isometric rigidity results from geometric group theory.

**March 4:** Funda Gul (Stevens Institute of Technology), *Distortion of embeddings of \tau-groups into group of untriangular matrices*
**Abstract: ** In this talk we will introduce some well-known embeddings of \tau-groups (non-abelian, finitely generated nilpotent groups) into group of unitriangular matrices. We will have a look at these embeddings from a geometric point of view and provide some results about the distortion of some of those embeddings. What we mean by the distortion of an embedding is the distortion of the image of \tau-group in the group of unitriangular matrices.

**April 1:** Dmitry Panteleev (Stevens Institute of Technology), * Conjugacy search problem and the Andrews--Curtis conjecture*
**Abstract: ** In this talk I will present some new
computational methods for studying
potential counterexamples to the Andrews--Curtis conjecture,
in particular, Akbulut--Kurby examples AK(n).
To improve metric properties of the search space
(which is a set of balanced presentations of a trivial group)
we consider a new transformation that generalizes
the original Andrews-Curtis transformations.
We will discuss details of a practical implementation of the new move
(which uses Pseudo-Conjugacy graphs) and methods
to reduce the number of pairs to be considered.

This is joint work with Sasha Ushakov.

**April 8:** Andrew Sale (Vanderbilt University), *The permutation conjugacy length function*
**Abstract: ** I will describe a geometric version of the conjugacy problem,
which involves determining the length of short conjugators between
elements in a group, and defining the conjugacy length function. I will
then explain recent work with Y. Antolin in which we define the
permutation conjugacy length function, a similar but more delicate
notion, which has the potential to form a base for a geometric study of
the conjugacy problem that yields fast algorithms solving the conjugacy
search problem.

**May 13:** Anand Sarwate (Rutgers University), *From local to distributed differential privacy*
**Abstract: ** Differential privacy has become a widely-studied framework for understanding how the results of computation on a database of individuals' private data can reveal information about individual records in the database. In this talk I will describe the differential privacy model and some connections to information theory. I will then discuss recent results on understanding local privacy-distortion tradeoffs from a rate-distortion perspective. Finally, I will describe ongoing work on designing differentially private algorithms for distributed data.

To subscribe to the seminar mailing list, click here