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 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.

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.

Monday, June 3, 2024 11:30 am - 12:30 pm EDT (GMT -04:00)

Algebraic Graph Theory - Wei Wang

Title: Which graphs are determined by their total numbers of walks?

Speaker: Wei Wang
Affiliation: Xi'an Jiaotong University
Location: Please contact Sabrina Lato for the Zoom link.

Abstract: Walks and closed-walks are ubiquitous in graph theory, which capture lots of important structural information of graphs. In this talk, we shall consider the question in the title. The same question for closed walks is precisely the problem of spectral characterizations of graphs. We show that for most graphs, the number of walks determines the generalized spectrum of graphs and vice versa. Then the above question is equivalent to the problem of generalized spectral characterizations of graphs, a topic which has been studied extensively in recent years. Some simple criterions are provided for graphs G to be determined by their total number of walks, based on some recent results on the generalized spectral characterizations of graphs. Numerical results are also provided to illustrate the effectiveness of the proposed method. This is a joint work with Weifang Lv, Finjin Liu and Wei Wang.

Tuesday, June 4, 2024 1:30 pm - 2:30 pm EDT (GMT -04:00)

URA Seminar - Nikhil Kumar

Title: Multicommodity Flows and Cuts

Speaker: Nikhil Kumar
Affiliation: University of Waterloo
Location:  MC 5501

Abstract: Flow and cut problems occupy a central place in discrete optimzation and algorithms. The well known max-flow min-cut theorem states that there exists a s-t flow of value d in a network if and only if the minimum capacity of edges whose removal separates s and t is at least d. In this talk, we will discuss a generalization of this problem to the multicommodity setting and study natural necessary and sufficient conditions for the existence of a feasible flow. We will discuss connections to approximation algorithms, metric embeddings and partitions, and survey some of the classical results, open problems and recent progress.