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, April 27, 2018 — 3:30 PM EDT
Title: Spins Lattices, Graphs and Quantum State Revivals
| Speaker: | Luc Vinet |
| Affiliation: | Université de Montréal |
| Room: | MC 5501 |
Abstract:
This talk will describe how certain features of quantum transport along spin chains can be enabled.
Friday, April 20, 2018 — 3:30 PM EDT
Title: Transversals in covers of graphs
| Speaker: | Krystal Guo |
| Affiliation: | Université Libre de Bruxelles |
| Room: | MC 5501 |
Abstract:
We study a polynomial with connections to correspondence colouring (also known as DP-colouring) and the Unique Games Conjecture.
Friday, April 13, 2018 — 3:30 PM EDT
Title: Interpolating between the characteristic and matching polynomials of a graph
| Speaker: | Chris Godsil |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
The characteristic polynomial Φ(X, t) of a graph X has two obvious combinatorial connections.
Wednesday, April 11, 2018 — 4:00 PM EDT
Title: Robust discrete optimization and network flows (paper by Bertsimas and Sim)
Friday, April 6, 2018 — 3:30 PM EDT
Title: Generating Functions: Theory, Algorithms, and Applications
| Speaker: | Stephen Melczer |
| Affiliation: | University of Pennsylvania |
| Room: | MC 5501 |
Abstract:
Generating functions are an invaluable tool in many areas of discrete mathematics and beyond.
Thursday, April 5, 2018 — 1:30 PM EDT
Title: Graphs and Unitals
Wednesday, April 4, 2018 — 4:00 PM EDT
Title: Robust Solutions of Optimization Problems Affected by Uncertain Probabilities (paper by Ben-Tal A et al )
Tuesday, April 3, 2018 — 10:00 AM EDT
Title: Erdos-Hajnal meets Gyarfas-Sumner
| Speaker: | Paul Seymour |
| Affiliation: | Princeton |
| Room: | QNC 1501 |
Abstract:
The Gyarfas-Sumner conjecture says that every graph with huge (enough) chromatic number and bounded clique number contains any given forest as an induced subgraph. (And non-forests do not have this property.)
Monday, April 2, 2018 — 1:00 PM EDT
There are 3 short talks this week.
Title: Quantum Collision-Finding in Non-Uniform Random Functions
| Speaker: | Ted Eaton |
| Affiliation: | ISARA Corporatio |
| Room: | MC 6486 |
Abstract: Proving the security of a scheme against a quantum adversary often makes the strong assumption of modelling the hash function as uniformly random. In this work, we study the generic security of non-uniform random functions, specifically those with min-entropy k. This has applications to the quantum security of the Fujisaki-Okamoto transformation, as well as allowing for more relaxed security assumptions. We discuss previous results and sketch a proof for an asymptotic upper and lower bound of 2k/3 quantum queries.