Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Friday, February 18, 2022 — 3:30 PM EST
Title: Densest Subgraph: Supermodularity, Iterative Peeling, and Flow
| Speaker: | Chandra Chekuri |
| Affiliation: | University of Illinois, Urbana-Champaign |
| Zoom: | Please email Emma Watson |
Abstract:
The densest subgraph problem in a graph (DSG), in the simplest form, is the following. Given an undirected graph G = (V, E) find a subset S of vertices that maximizes the ratio |E(S)|/|S| where E(S) is the set of edges with both endpoints in S. DSG and several of its variants are well-studied in theory and practice and have many applications in data mining and network analysis.
Tuesday, February 15, 2022 — 4:00 PM EST
Title: Homomorphism counts in robustly sparse graphs
| Speaker: | Chun-Hung Liu |
| Affiliation: | Texas A&M University |
| Zoom: | Click here or please email Shayla Redlin |
Abstract:
For a fixed graph H and for arbitrarily large host graphs G, the number of homomorphisms from H to G and the number of subgraphs isomorphic to H contained in G have been extensively studied when the host graphs are allowed to be dense.
Monday, February 14, 2022 — 11:30 AM EST
Title: On reverse mixing in quantum walks
| Speaker: | Christino Tamon |
| Affiliation: | Clarkson University |
| Zoom: | Contact Sabrina Lato |
Abstract:
A random walk on a connected undirected graph mixes to the principal eigenvector. We consider a continuous-time quantum walk to reverse this process: starting with the principal eigenvector, can we reach an arbitrary vertex if we were to place a loop on the target vertex?
Thursday, February 10, 2022 — 1:00 PM EST
Title: A curious identity between the orthogonal Brezin--Gross--Witten integral and Schur symmetric functions via b-deformed monotone Hurwitz numbers
| Speaker: | Maciej Dolega |
| Affiliation: | IMPAN |
| Zoom: | Please email Olya Mandelshtam |
Abstract:
This talk is intended for an algebraic combinatorial community and no prior knowledge is required. All the difficult words (Hurwitz numbers, KP hierarchy, HCIZ and BGW integrals, Jack symmetric functions, the b-conjecture) will be explained and gently introduced.
Thursday, February 10, 2022 — 10:30 AM EST
Title: Rotational Differential-Linear Cryptanalysis of ARX Ciphers
| Speaker: | Siwei Sun |
| Affiliation: | University of Chinese Academy of Sciences |
| Zoom: | Please email Jesse Elliott |
Abstract:
The differential-linear attack, combining the power of the two most effective techniques for symmetric-key cryptanalysis, was proposed by Langford and Hellman at CRYPTO 1994. We further extend this framework by replacing the differential part of the attack by rotational differentials.
Tuesday, February 8, 2022 — 3:00 PM EST
Title: Two counterexamples related to chi-boundedness
| Speaker: | Sophie Spirkl and James Davies |
| Affiliation: | University of Waterloo |
| Zoom: | Click here or please email Shayla Redlin |
Abstract:
This will be a joint talk with two parts.
Sophie Spirkl: I will present a counterexample to the following well-known conjecture: for every k, r, every graph G with clique number at most k and sufficiently large chromatic number contains a triangle-free induced subgraph with chromatic number at least r.
Monday, February 7, 2022 — 11:30 AM EST
Title: Optimizing sums of eigenvalues
| Speaker: | Gabriel Coutinho |
| Affiliation: | Universidade Federal de Minas Gerais |
| Zoom: | Contact Sabrina Lato |
Abstract:
In its original proof, Hoffman's well known lower bound to the chromatic number is obtained after replacing several terms of a sum of eigenvalues by the smallest eigenvalue of the graph.
Friday, February 4, 2022 — 3:30 PM EST
Title: The Problem Landscape of SIDH
| Speaker: | David Jao |
| Affiliation: | University of Waterloo |
| Zoom: | Please email Emma Watson |
Abstract:
The Supersingular Isogeny Diffie-Hellman protocol (SIDH) has recently been the subject of increased attention in the cryptography community. Conjecturally quantum-resistant, SIDH has the feature that it shares the same data flow as ordinary Diffie-Hellman: two parties exchange a pair of public keys, each generated from a private key, and combine them to form a shared secret.
Thursday, February 3, 2022 — 1:00 PM EST
Title: Semidistrim Lattices
| Speaker: | Colin Defant |
| Affiliation: | Princeton University |
| Zoom: | Please email Olya Mandelshtam |
Abstract:
This talk will introduce semidistrim lattices, which generalize semidistributive lattices and trim lattices; these two families, in turn, generalize distributive lattices. We will discuss structural, topological, and dynamical properties of semidistrim lattices. In particular, we will see how one can define a certain bijective operator on a semidistrim lattice called rowmotion; this definition unifies the definition that Barnard gave for semidistributive lattices and the definition that Thomas and Williams gave for trim lattices.
Tuesday, February 1, 2022 — 3:00 PM EST
Title: Strong components of the directed configuration model
| Speaker: | Matthew Coulson |
| Affiliation: | University of Waterloo |
| Zoom: | http://matroidunion.org/?page_id=2477 or please email Shayla Redlin |
Abstract:
We study the behaviour of the largest components of the directed configuration model in the barely subcritical regime. We show that with high probability all strongly connected components in this regime are either cycles or isolated vertices and give an asymptotic distribution of the size of the kth largest cycle. This gives a configuration model analogue of a result of Luczak and Seierstad for the binomial random digraph.