Please email any errors or updates to our website support/editor.
PDF files require Adobe Acrobat Reader.
Friday, January 15, 2021 — 3:30 PM EST
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.
Monday, January 18, 2021 — 11:30 AM EST
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.
Thursday, January 21, 2021 — 1:30 PM EST
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.
Friday, January 22, 2021 — 3:30 PM EST
Title: Fast simulation of planar Clifford circuits
| Speaker: | David Gosset |
| Aflliation: | University of Waterloo |
| Zoom: | Please email Emma Watson |
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.