Events

Title: Abelian covers of association schemes with applications to SIC-POVM

Abstract: Godsil and Hensel (1992) developed a theory of abelian covers of complete graphs to construct antipodal distance-regular graphs of diameter 3. More recently, Coutinho, Godsil, Shirazi and Zhan (2016) showed that equiangular tight frames can be constructed from covers of complete graphs in terms of cyclic groups of prime order. In this talk, we introduce covers of (not necessarily symmetric) association scheme of d classes in terms of an (not necessarily cyclic) abelian group G of order d.

Title: Lorentzian polynomials

Abstract: Lorentzian (aka completely log-concave) polynomials were recently developed by Brändén-Huh and Anari-Liu-Oveis Gharan-Vinzant to settle Mason's conjectures on the log-concavity of the number of size-k independent sets of a matroid. In this talk, we will define these polynomials and sketch the proof of these conjectures. Along the way we will also state other results which will demonstrate the very strong connection between matroids and Lorentzian polynomials.

Title: Deza graphs and vertex connectivity

Abstract: A k-regular graph on v vertices is called a Deza graph with parameters (v, k, b, a), b ≥ a if the number of common neighbors of any two distinct vertices takes two values: a or b. A Deza graph is called a strictly Deza graph if it has diameter 2 and is not strongly regular.

In this talk we will discuss the enumeration of strictly Deza graphs and the enumeration of special subclass of strictly Deza graphs called divisible design graphs. We will also describe the constructions of divisible design graphs found during the enumeration.

Title: Configuration spaces and combinatorial algebras

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm.

Abstract:  In this talk, I will discuss connections between configuration spaces, an important class of topological space, and combinatorial algebras arising from the theory of reflection groups. In particular, I will present work relating the cohomology rings of some classical configuration spaces—such as the space of n ordered points in Euclidean space—with Solomon’s descent algebra and the peak algebra. The talk will be centered around two questions.

First, how are these objects related?

Second, how can studying one inform the other? This is partially joint work with Marcelo Aguiar and Vic Reiner.

Title: Stochastic  Oracles and Where to Find Them

Abstract: Continuous optimization is a mature field, which has recently undergone major expansion and change. One of the key new directions is the development of methods that do not require exact information about the objective function. Nevertheless, the majority of these methods, from stochastic gradient descent to "zero-th order" methods use some kind of approximate first order information. We will overview different methods of obtaining this information, including simple stochastic gradient via sampling, robust gradient estimation in adversarial settings, traditional and randomized finite difference methods and more.

We will discuss what key properties of these inexact, stochastic first order oracles are useful for convergence analysis of optimization methods that use them. 

Title: Adventures in Enumeration

Abstract: We make the argument that by combining pure mathematical tools with computational insights and applications from a vast array of disciplines, combinatorics is the perfect area to see all the wonders of math on display. Applications discussed include the analysis of classical algorithms, restricted permutations, models predicting the shape of biomembranes, queuing theory, random walks, ratchet models for gene expression, maximum likelihood degree in algebraic statistics, transcendence of zeta values, sampling algorithms for perfect matchings in bipartite graphs, and parallel synthesis for DNA storage.

Title: Reconstructing Shredded Random Matrices

Abstract: The Graph Reconstruction Conjecture states that if we are given the set of vertex-deleted subgraphs of some graph, then there is a unique graph G that can be reconstructed from them. This conjecture has been open since the 60s, and has only been solved for certain classes of graphs with not much progress towards the general case. We instead study adjacent reconstruction problems, for example, studying matrices instead of graphs:  Given some binary matrix M, suppose we are presented with the collection of its rows and columns in independent arbitrary orderings. From this information, are we able to recover the original matrix and will it be unique? We present an algorithm that identifies whether there is a unique ordering associated with a set of rows and columns, and outputs either the unique correct orderings for the rows and columns or the full collection of all valid orderings and valid matrices. We show that for matrices with entries that are i.i.d. Bernoulli(p), that for p >2log(n)/n that the matrix is indeed unique with high probability. This is a joint work with Caelan Atamanchuk and Luc Devroye.

Title: Sylvester-Gallai type configurations and Polynomial Identity Testing

Abstract: The classical Sylvester-Gallai theorem in combinatorial geometry says the following:

If a finite set of points in the Euclidean plane has the property that the line joining any two points contains a third point from the set, then all the points must be collinear. 

More generally, a Sylvester-Gallai (SG)-type configuration is a finite set of geometric objects with certain local dependencies. A remarkable phenomenon is that the local constraints give rise to global dimension bounds for linear SG-type configurations, and such results have found far reaching applications to complexity theory and coding theory. In particular, SG-type configurations have been extremely useful in applications to Polynomial Identity Testing (PIT), a central problem in algebraic complexity theory.

In this talk, we will discuss non-linear generalizations of SG-type configurations which consist of polynomials. We will discuss how uniform bounds on SG-configurations give rise to deterministic poly-time algorithms for the PIT problem. I’ll talk about results showing that these non-linear SG-type configurations are indeed low-dimensional as conjectured by Gupta in 2014. This is based on joint works with A. Garg, R. Oliveira and S. Peleg.

Title: The spectra of lift and factored lifts of graphs or digraphs

Abstract: In this talk, we first explain the path we took from defining polynomial matrices to a generalization of voltage graphs that we call combined voltage graphs. Moreover, we give a general definition of a matrix associated with a combined voltage graph, which allows us to provide a new method for computing the eigenvalues and eigenspaces of such graphs. 

Title: Sometimes you can't compute on encrypted data 

Abstract: A long dream in cryptography was "fully homomorphic encryption": the ability to perform computations on encrypted data. This way, a cloud provider can do your computations without compromising your privacy. The first general method was proposed by Gentry in 2009, but this method and follow up works are all too slow for many purposes. Naturally, we want to do better. This talk will explain some work in progress from a pessimistic perspective: when can we prove that faster methods are impossible.