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, November 29, 2019 — 3:30 PM EST
Title: Incompressibility of classical distributions
| Speaker: | Debbie Leung |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
We prove a general, robust, single-letter lower bound on the achievable rate for ensembles of classical states, which holds even when Alice and Bob share free entanglement and allow a constant local error.
Thursday, November 28, 2019 — 4:00 PM EST
Title: Resilience of the rank of random matrices
| Speaker: | Jorn van der Pol |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
I will discuss the preprint of this title by Ferber, Luh, and McKinley (arXiv:1910.03619).
Friday, November 22, 2019 — 3:30 PM EST
Title: Disjunctive Cuts through the V-Polyhedral Lens
| Speaker: | Aleksandr Kazachkov |
| Affiliation: | Polytechnique Montréal |
| Room: | MC 5501 |
Abstract:
Cutting planes, or cuts, are a critical component of modern integer programming solvers, but existing cuts implemented in solvers are relatively simple compared to those in the literature. We discuss the primary reasons for this disparity, as well as our recently-proposed V-polyhedral framework for mitigating some of these difficulties encountered by prior "stronger" cuts.
Friday, November 22, 2019 — 1:00 PM EST
Title: Submodular function maximization via the multilinear relaxation and contention resolution schemes
| Speaker: | Sharat Ibrahimpur |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
I will present a general framework for maximizing a nonnegative submodular set function $f$ subject to a variety of packing type constraints including multiple matroid constraints, knapsack constraints, and their intersections.
Thursday, November 21, 2019 — 4:00 PM EST
Title: Kummer's Theorem on binomial coefficients, etc.
| Speaker: | John Schanck |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
Some of us like the primes and call ourselves pure mathematicians. Some of us like the Catalan numbers and call ourselves combinatorialists.
Friday, November 15, 2019 — 3:30 PM EST
Title: The combinatorics of parametric Feynman integrals
| Speaker: | Marcel Golz |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
Feynman integrals are used in perturbative quantum field theory to compute the probabilities of processes involving elementary particles. They can be represented as Feynman graphs and exhibit a rich combinatorial structure. The parametric representation of Feynman integrals is particularly suitable to be studied from a combinatorial perspective since it contains well known objects like the Kirchhoff polynomial.
Friday, November 15, 2019 — 1:00 PM EST
Title: A deterministic (1/2 + epsilon)-approximation for submodular maximizztion over a matroid
| Speaker: | Ben Moore |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
In 1978, it was shown that a natural greedy algorithm gives a 1/2 approximation to submodular maximization subject to a matroid constraint.
Thursday, November 14, 2019 — 4:00 PM EST
Title: Halfway to Rota's Basis Conjecture
| Speaker: | Shayla Redlin |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
Rota’s Basis Conjecture is that any rank-n matroid with n disjoint bases B_1, …, B_n has n disjoint transversal bases; a basis is transversal if it contains exactly one element from each B_i.
Thursday, November 14, 2019 — 3:00 PM EST
Title: From weakly separated collections to matroid subdivisions
| Speaker: | Nick Early |
| Affiliation: | Perimeter Institute for Theoretical Physics |
| Room: | MC 5417 |
Abstract:
We study arrangements of slightly skewed tropical hyperplanes, called blades, on the vertices of a hypersimplex $\Delta_{k,n}$.
Friday, November 8, 2019 — 3:30 PM EST
Title: Circuit-hyperplane relaxation and matroid representation
| Speaker: | Jim Geelen |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
Relaxing a circuit-hyperplane in a representable matroid can destroy representability.
Thursday, November 7, 2019 — 4:00 PM EST
Title: Counting Pentagons in Triangle-free Binary Matroids
| Speaker: | Adam Brown |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
Every triangle-free graph with n vertices contains at most (n/5)^5 cycles of length five, and this value is attained by the balanced blowup of the 5-cycle.
Thursday, November 7, 2019 — 3:00 PM EST
Title: Two-colouring hypersurface complements in open Richardson varities
| Speaker: | Kevin Purbhoo |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
Given an algebraic hypersurface $H \subset \mathbb{R}^n$, we can always 2-colour the components of the complement $\mathbb{R}^n \setminus H$ such that adjacent components are of opposite colours.
Thursday, November 7, 2019 — 1:00 PM EST
Title: Cospectral and strongly cospectral vertices
| Speaker: | Chris Godsil |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
If $a$ is a vertex in a graph with adjacency matrix $A$, the \textsl{walk module} generated by $a$ is the $A$-invariant subspace spanned by the vectors $A^re_a$, for $r\ge0$.
Friday, November 1, 2019 — 3:30 PM EDT
Title: A Quantum Query Complexity Trichotomy for Regular Languages
| Speaker: | Luke Schaeffer |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
We consider the quantum query complexity of regular languages and discover a surprising trichotomy: each regular language has query complexity either Theta(1), ~Theta(sqrt(n)) or Theta(n).
Friday, November 1, 2019 — 1:00 PM EDT
Title: Maximizing non-monotone submodular functions
| Speaker: | Zishen Qu |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
Optimization of non-monotone submodular functions has applications in the maximum cut and maximum directed cut problems for graphs.