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:
Monday, June 24, 2024 1:00 pm - 2:00 pm EDT (GMT -04:00)

C&O Reading Group - Rian Neogi

Title: Bipartite Perfect Matching is in Quasi-NC

Speaker: Rian Neogi
Affiliation: University of Waterloo
Location: MC 6029

Abstract: Mulmuley, Vazirani, and Vazirani gave a randomized parallel algorithm for checking whether a perfect matching exists in a graph. In doing so, they came up with the infamous isolation lemma, which found several uses in other areas of computer science. The isolation lemma is inherently randomized, and it has been a long-standing open problem to derandomize the lemma. In this talk, I will go over the breakthrough work of Fenner, Gurjar, and Thierauf where they almost completely derandomize the isolation lemma in the special case when applied to the bipartite perfect matching problem. In doing so, they give a deterministic parallel algorithm for perfect matching that uses a quasi-polynomial number of processors.

Thursday, June 27, 2024 2:00 pm - 3:00 pm EDT (GMT -04:00)

Algebraic and Enumerative Combinatorics - Paul Balduf

Title: Combinatorial proof of a Non-Renormalization Theorem

Speaker: Paul Balduf
Affiliation: University of Waterloo
Location: MC 5479

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

Abstract: In "Higher Operations in Perturbation Theory", Gaiotto, Kulp, and Wu discussed Feynman integrals that controls certain deformations in quantum field theory. These integrals themselves are differential forms, and the authors conjectured that one class of them squares to zero. This phenomenon can be interpreted as absence of quantum corrections in topological quantum field theories with more than one topological direction, or as an analogue of Kontsevich's formality theorem. In my talk, I will present a purely combinatorial proof of the conjecture for arbitrary graphs. It is based on graph matrices and graph polynomials, and a careful analysis of the involved signs and multiplicities. No knowledge or intution of the underlying physics is required.

In the preseminar, I will review the necessary definitions and properties of graph polynomials, and how they are typically applied in Feynman integrals. If time permits, I might also comment on the physical background.

Friday, June 28, 2024 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte Colloquium - Jason Gao

Title: Graph Embeddings and Map Colorings

Speaker: Jason Gao
Affiliation: Carleton University
Location: MC 5501

Abstract: The famous  Map Color Theorem says that the chromatic number of a surface of Euler characteristic $c<0$ is equal to $\displaystyle \left\lfloor \frac{1}{2}\left(7+\sqrt{49-24c}\right)\right\rfloor $. This was proved in 1969 by Ringel and Youngs who showed that $K_n$ can be embedded on surfaces of Euler characteristic $c$ such that $\displaystyle n= \left\lfloor \frac{1}{2}\left(7+\sqrt{49-24c}\right)\right\rfloor $. This leads to the study about the  genus distribution of a graph $G$, that is, the number of embeddings of $G$ on surfaces. This talk will go through some recent results about genus distributions of bouquets and cubic graphs.  Some results and conjectures will also be given about the distribution of the  chromatic number of a random map on a given surface.

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

URA Seminar - Thomas Lesgourgues

Title: On the use of senders in Ramsey Theory

Speaker: Thomas Lesgourgus
Affiliation: University of Waterloo
Location: MC 5479

Abstract: In this talk I will introduce and investigate some parameters in Graph Ramsey theory, beyond the traditional Ramsey numbers. A crucial ingredient for their analysis is the existence of gadget graphs, called signal senders, that were initially developed by Burr, Erdős and Lovász in 1976. I will explain their origin, properties, and try to convey their surprising strength. Using probabilistic methods, we will see how to build such gadgets, and how to use them to prove some theorems, previously out of reach without these tools.

Tuesday, July 2, 2024 3:00 pm - 4:00 pm EDT (GMT -04:00)

Graphs and Matroids - Bertrand Guenin

Title: A relaxation of Woodall’s conjecture

Speaker: Bertrand Guenin
Affiliation: University of Waterloo
Location: MC 5479

Abstract: In a directed graph, a directed cut (dicut for short) is a cut where all arcs are directed from one shore to the other; a directed join (dijoin for short) is a set of arcs whose contraction makes the digraph strongly connected. The celebrated Lucchesi–Younger theorem states that for any directed graph the size of the smallest dijoin equals the maximum number of pairwise disjoint dicuts. Woodall’s conjecture posits that the size of the smallest dicut equals the maximum number of pairwise disjoint dijoins. 

Friday, July 5, 2024 1:00 pm - 2:00 pm EDT (GMT -04:00)

C&O Reading Group - Rian Neogi

Title: Bipartite Perfect Matching is in Quasi-NC, Part II

Speaker: Rian Neogi
Affiliation: University of Waterloo
Location: MC 6029

Abstract: Mulmuley, Vazirani, and Vazirani gave a randomized parallel algorithm for checking whether a perfect matching exists in a graph. In doing so, they came up with the infamous isolation lemma, which found several uses in other areas of computer science. The isolation lemma is inherently randomized, and it has been a long-standing open problem to derandomize the lemma. In this talk, I will go over the breakthrough work of Fenner, Gurjar, and Thierauf where they almost completely derandomize the isolation lemma in the special case when applied to the bipartite perfect matching problem. In doing so, they give a deterministic parallel algorithm for perfect matching that uses a quasi-polynomial number of processors.

Friday, July 5, 2024 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte Colloquium - Leonardo Colo'

Title: Supersingular isogeny graphs, modular curves and Galois Representations.

Speaker: Leonardo Colo'
Affiliation: University of Waterloo
Location: MC 5501

Abstract: In this talk we will discuss the remarkable interconnection among supersingular elliptic curves, modular curves and Galois representations with a focus on cryptographic applications.

Tuesday, July 9, 2024 1:30 pm - 2:30 pm EDT (GMT -04:00)

URA Seminar - Kanstantsin Pashkovich

Title: Contracts for Functions Based on Graphs

Speaker: Kanstantsin Pashkovich
Affiliation: University of Waterloo
Location: MC 5479

Abstract: We study contracts for combinatorial problems in multi-agent settings. In this problem, a principal designs a contract with several agents, whose actions the principal is unable to observe. The principal is able to see only the outcome of the agents' collective actions; and the outcome is either a success or failure. All agents that decided to exert effort incur costs, and so naturally all agents expect a fraction of the principal's reward as a compensation. The principal needs to decide what fraction of their reward to give to each agent so that the principal's expected utility is maximized.

Friday, July 12, 2024 1:00 pm - 2:00 pm EDT (GMT -04:00)

C&O Reading Group - Sina Kalantarzadeh

Title: Approximating Graphic TSP with matchings

Speaker: Sina Kalantarzadeh
Affiliation: University of Waterloo
Location: MC 6029

Abstract: Revisiting defining character of the field of algorithm design and complexity, TSP!. While the problem itself is NP-Hard and difficult to approximate, various formulations, such as the Metric version, have yielded notable approximation algorithms. The classical 1.5-approximation algorithm by Christofides, leveraging matchings, stood as the best-known result for decades. However, recent breakthroughs have pushed these boundaries further.

Friday, July 12, 2024 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte Colloquium - Patricia Klein

Title: Combinatorial models in enumerative geometry

Speaker: Patricia Klein
Affiliation: Texas A&M University
Location: MC 5501

Abstract: How many circles are tangent to three given circles in the plane?  How many lines lie on a smooth cubic surface? How many lines intersect four given lines in 3-space? These are classical questions in enumerative geometry, a field at least as old as Apollonius of Perga, to whom the question about tangent circles is attributed in the third century BCE.  It is not hard to see that the answers to these questions may depend on the choice of circles, surface, or lines, respectively. It is harder to see that, in each case, there is a "typical" answer.