Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Title: OutFn, M_gn and renormalized topological field theory
Speaker: | Michael Borinsky |
Affiliation: | Nikhef |
Room: | MC 5417 |
Abstract:
I will report on recent joint work with Karen Vogtmann on the Euler characteristic of Out(F_n) and the moduli space of graphs.
Title: Graph covers with two new eigenvalues
Speaker: | Olha Silina |
Affiliation: | University of Waterloo |
Room: | MC 5479 |
Abstract:
I am going to talk about graph covers. If $Y$ is a cyclic cover of $X$, it turns out that $Y$ has the same spectrum as $X$ plus (possibly) some new eigenvalues.
Title: Biometric security: Design, implementation, and challenges
Speaker: | Koray Karabina |
Affiliation: | Florida Atlantic University |
Room: | MC 5501 |
Abstract:
Biometric based cybersecurity technologies offer significant advantages in authentication, identification, and access control mechanisms.
Title: Inverses of Trees
Speaker: | Krystal Guo |
Affiliation: | Centre de Recherches Mathématiques & Université de Montréal |
Room: | MC 5417 |
Abstract:
A tree is invertible if and only if it has a perfect matching.
Godsil considers an invertible tree T and finds that the inverse of the adjacency matrix has entries in {0, ±1} and is the signed adjacency matrix of a graph which contains T.
Title: How can we optimize nonsmooth objectives globally?
Speaker: | Andreas Griewank |
Affiliation: | Humboldt University, Germany |
Room: | MC 5501 |
Abstract:
In machine learning objective functions that are only piecewise smooth and should be globally minimized abound. The standard method of dealing with them is to apply a stochastic gradient method disregarding the rare points of nonsmoothness and hoping for the best as far as global optimality of the computed solution is concerned.
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.
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).
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.
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.
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.
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.
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.
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.
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}$.
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.
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.
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.
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$.
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).
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.
Title: Edge-maximal graphs on surfaces
Speaker: | James Davies |
Affiliation: | University of Waterloo |
Room: | MC 5501 |
Abstract:
It is straightforward to show that, with the exception of small complete graphs, every edge-maximal planar graph triangulates the plane.
Title: Interpolated versions of the Central Limit Theorem, and crossings of pair-partitions
Speaker: | Alexandru Nica |
Affiliation: | University of Waterloo |
Room: | MC 5417 |
Abstract:
Title: Perfect state transfer on Cayley graphs
Speaker: | Soffia Arnadottir |
Affiliation: | University of Waterloo |
Room: | MC 5479 |
Abstract:
Perfect state transfer on Cayley graphs
Title: Cutting a square into triangles of equal area
Speaker: | Hayley Reid |
Affiliation: | University of Waterloo |
Room: | MC 5501 |
Abstract:
Suppose you are given a square and asked to cut it into n triangles of equal area. If n is even the problem is almost trivial, but when n is odd the problem becomes much harder.
Title: Sublinear separators in intersection graphs of convex shapes
Speaker: | Rose McCarty |
Affiliation: | University of Waterloo |
Room: | MC 5501 |
Abstract:
A balanced separator of an n-vertex graph is set of vertices whose deletion leaves only components of size at most 2n/3.
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.