Events by month

Title: Complex Hadamard diagonalizable graphs

Speaker: Ada Chan Affiliation: York University Zoom Contact: Soffia Arnadottir

Abstract: 

A graph is complex Hadamard diagonalizable if its Laplacian matrix is diagonalizable by a complex Hadamard matrix.

This is a natural generalization of the Hadamard diagonalizable graphs introduced by Barik, Fallat and Kirkland.

My interest in these graphs is two-fold:

Title: K-fractional revival and approximate K-fractional revival on path graphs

Speaker: Whitney Drazen Affiliation: Northeastern University Zoom: Contact Soffia Arnadottir

Abstract:

A continuous-time quantum walk is a process on a network of quantum particles that is governed by the transition matrix U(t) = e^{-itA}, where is A is the adjacency matrix of the graph. The two-vertex phenomenon fractional revival occurs between vertices u and v at time t if the columns of U(t) corresponding to u and v are only supported on the rows indexed by those same two vertices. The well-studied perfect state transfer is a special case of this.

Title: Analytic Combinatorics, Rigorous Numerics, and Uniqueness of Biomembranes

Speaker: Steve Melczer Affiliation: University of Waterloo Zoom: Contact Karen Yeats

Abstract:

Since the invention of the compound microscope in the early seventeenth century, scientists have marvelled over red blood cells and their surprising shape. An influential model of Canham predicts the shapes of blood cells and similar biomembranes come from a variational problem minimizing the "bending energy" of these surfaces. Because observed (healthy) cells have the same shape in humans, it is natural to ask whether the model admits a unique solution. Here, we prove solution uniqueness for the genus one Canham problem.

Title: Finding and Counting k-cuts in Graphs

Speaker: Anupam Gupta Affiliation:

Carnegie Mellon University

Zoom: Please email Emma Watson

Abstract:

For an undirected graph with edge weights, a k-cut is a set of edges whose deletion breaks the graph into at least k connected components. How fast can we find a minimum-weight k-cut? And how many minimum k-cuts can a graph have? The two problems are closely linked. In 1996 Karger and Stein showed how to find a minimum k-cut in approximately n^{2k-2} time; their proof also bounded the number of minimum k-cuts by n^{2k-2}, using the probabilistic method.

Title: Various Maximum Nullities Associated with a Graph

Speaker: Shaun Fallat Affiliation: University of Regina Zoom: Contact Soffia Arnadottir

Abstract:

Given a graph, we associate a collection of (typically symmetric) matrices S whose pattern of non-zero entries off of the main diagonal respects the edges in the graph. To this set, we let M denote the maximum possible nullity over all matrices in S. Depending on the choice of the set S, and the family of graphs considered, the parameter M often corresponds to an interesting combinatorial characteristic (planarity, connectivity, coverings, etc.) of the underlying graph.

Title: The growth of groups and algebras

Speaker: Jason Bell Affiliation: University of Waterloo Zoom: Contact Karen Yeats

Abstract:

We give an overview of the theory of growth functions for associative algebras and explain their significance when trying to understand algebras from a combinatorial point of view.  We then give a classification for which functions can occur as the growth function of a finitely generated associative algebra up to asymptotic equivalence. This is joint work with Efim Zelmanov.

Title: Fast simulation of planar Clifford circuits

Speaker: David Gosset Aflliation: University of Waterloo YouTube Link: https://youtu.be/LjmjiEPTSNo

Abstract:

Clifford circuits are a special family of quantum circuits that can be simulated on a classical computer in polynomial time using linear algebra. Recent work has shown that Clifford circuits composed of nearest-neighbor gates in planar geometries can solve certain linear algebra problems provably faster --as measured by circuit depth-- than classical computers.

Title: The Matchings Polynomial

Speaker: Chris Godsil Affiliation: University of Waterloo Zoom: Contact Soffia Arnadottir

Abstract:

A $k$-matching in a graph is a matching of size $k$, and $p(X,k)$ denotes the number of $k$-matchings in $X$.

The matching polynomial of a graph is a form of generating function for the sequence $(p(X,k))_{k\ge0}$.

If is closely related to the characteristic polynomial of a graph. I will discuss some of the many interesting properties of this polynomial, and some of the related open problems.

Title: The multispecies TAZRP and modified Macdonald polynomials

Speaker: Olya Mandelshtam Affiliation: University of Waterloo Zoom: Contact Karen Yeats

Abstract:

Recently, a formula for the symmetric Macdonald polynomials $P_{\lambda}(X;q,t)$ was given in terms of objects called multiline queues, which also compute probabilities of a statistical mechanics model called the multispecies asymmetric simple exclusion process (ASEP) on a ring. It is natural to ask whether the modified Macdonald polynomials $\widetilde{H}_{\lambda}(X;q,t)$ can be obtained using a combinatorial gadget for some other statistical mechanics model.

Title: Finding twin smooth integers for isogeny-based cryptography

Speaker: Michael Naehrig Affliation: Microsoft Research Zoom: Please email Emma Watson

Abstract:

Efficient and secure instantiations of cryptographic protocols require careful parameter selection. For the isogeny-based cryptographic protocol B-SIDH, a variant of the Supersingular-Isogeny Diffie Hellman (SIDH) key exchange, one needs to find two consecutive B-smooth integers of cryptographic size such that their sum is prime. The smaller the smoothness bound B is, the more efficient the protocol becomes. This talk discusses a sieving algorithm to find such twin smooth integers that uses solutions to the Prouhet-Tarry-Escott problem.