Events

Filter by:

Limit to events where the first date of the event:
Date range
Limit to events where the first date of the event:
Limit to events where the title matches:
Limit to events where the type is one or more of:
Limit to events tagged with one or more of:
Limit to events where the audience is one or more of:
Tuesday, May 21, 2024 1:30 pm - 2:30 pm EDT (GMT -04:00)

URA Seminar - Stephen Melczer

Title: Adventures in Enumeration

Speaker: Stephen Melczer
Affiliation: University of Waterloo
Location: MC 5479

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.

Tuesday, May 21, 2024 3:00 pm - 4:00 pm EDT (GMT -04:00)

Graphs and Matroids - Massimo Vicenzo

Title: Reconstructing Shredded Random Matrices

Speaker: Massimo Vicenzo
Affiliation: University of Waterloo
Location: MC 5479

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.

Thursday, May 23, 2024 2:00 pm - 3:00 pm EDT (GMT -04:00)

Algebraic and Enumerative Combinatorics - Li Yu

Title: Integrable systems on the dual space of Lie algebras arising from log-canonical cluster structures

Speaker: Li Yu
Affiliation: University of Toronto
Location: MC 6029

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

Abstract: Let $(X, \{~,~\})$ be an (affine) Poisson variety. A log-canonical cluster structure on $X$ is a cluster structure on the coordinate ring of $X$ such that $\{\phi, \psi\} = \text{const} \cdot \phi \psi$ whenever $\phi, \psi$ are cluster variables which belong to the same cluster. When the Poisson bivector vanishes at some point $x \in X$, the tangent space $T_x X$ comes equipped with a Poisson bracket $\{~,~\}^{\text{lin}}$, the linearization of $\{~,~\}$.  Given a function $\phi$ on $X$, we propose a way of linearizing it to get a function $\phi^{\text{lin}}$ on $T_x X$. Very often, when $\{\phi_1, \cdots, \phi_n\}$ is a cluster in a log-canonical cluster structure on $(X, \{~,~\})$, $\{\phi_1^{\text{lin}}, \cdots, \phi_n^{\text{lin}}\}$ is an integrable system on $(T_x X, \{~,~\}^{\text{lin}})$.  We present two scenarios where this is the case.

Friday, May 24, 2024 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte Colloquium - Akash Sengupta

Title: Sylvester-Gallai type configurations and Polynomial Identity Testing

Speaker: Akash Sengupta
Affiliation: University of Waterloo
Location: MC 5501

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.

Tuesday, May 28, 2024 11:30 am - 12:30 pm EDT (GMT -04:00)

Algebraic Graph Theory - Cristina Dalfó

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

Speaker: Cristina Dalfó
Affiliation: Universitat de Lleida
Location: Please contact Sabrina Lato for Zoom Link.

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. 

Tuesday, May 28, 2024 1:30 pm - 2:30 pm EDT (GMT -04:00)

URA Seminar - Sam Jaques

Title: Sometimes you can't compute on encrypted data 

Speaker: Sam Jaques
Affiliation: University of Waterloo
Location: MC 5479

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.

Wednesday, May 29, 2024 3:30 pm - 4:30 pm EDT (GMT -04:00)

C&O Special Seminar - Vijay Vazirani

Title: A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length - Part 1

Speaker: Vijay Vazirani
Affiliation: University of California, Irvine
Location: MC 5479

Abstract: It is well known that the proof of some prominent results in mathematics took a very long time --- decades and even centuries. The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed --- over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max-flow.

The new ideas contained in the MV algorithm and its proof remain largely unknown, and hence unexplored, for use elsewhere.

The purpose of this two-talk-sequence is to rectify that shortcoming.

Thursday, May 30, 2024 2:00 pm - 3:00 pm EDT (GMT -04:00)

Algebraic & Enumerative Combinatorics - Jette Gutzeit

Title: Introducing the interval poset associahedron

Speaker: Jette Gutzeit
Affiliation: University of Greifswald
Location: MC 5479

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

Abstract: Given a permutation, we define its interval poset to be the set of all intervals ordered by inclusion. In this framework, a 'tube' is a convex connected subset, while a 'tubing' denotes a collection of tubes, that are pairwise either nested or disjoint. The interval poset associahedron is a polytope, whose faces correspond to proper tubes and whose vertices correspond to maximal tubings of the interval poset of a given permutation.

If we start with a simple permutation, the resulting interval poset associahedron will be isomorphic to the permutahedron. And if we consider inverse permutations, it turns out, that they yield identical associahedra.

If there is time, I will discuss another order on permutations, the Bruhat order, and compare it to the permutahedron.

Thursday, May 30, 2024 3:30 pm - 4:30 pm EDT (GMT -04:00)

C&O Special Seminar - Vijay Vazirani

Title: A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length - Part 2

Speaker: Vijay Vazirani
Affiliation: University of California, Irvine
Location: MC 5479

Abstract: It is well known that the proof of some prominent results in mathematics took a very long time --- decades and even centuries. The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed --- over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max-flow.

The new ideas contained in the MV algorithm and its proof remain largely unknown, and hence unexplored, for use elsewhere.

The purpose of this two-talk-sequence is to rectify that shortcoming.

Friday, May 31, 2024 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte Colloquium - Peter Nelson

Title: Infinite matroids on lattices

Speaker: Peter Nelson
Affiliation: University of Waterloo
Location: MC 5501

Abstract: There are at least two well-studied ways to extend matroids to more general objects - one can allow the ground set to be infinite, or instead define the concept of independence on a lattice other than a set lattice. I will discuss some nice ideas that arise when combining these two generalizations. This is joint work with Andrew Fulcher.