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, October 26, 2018 3:30 PM EDT
Title: Vertex Minors
| Speaker: | Jim Geelen |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
I will give an introduction to vertex-minors of graphs. At first sight vertex minors are a bit peculiar but they are closely related to graph minors and possibly even easier to work with.
Friday, October 26, 2018 1:00 PM EDT
Title:Local Search Guarantees on Facility Location Problems
| Speaker: | Zishen Qu |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract: We will show that guarantees can be given on algorithms for the k-median problem based on local search heuristics.
Thursday, October 25, 2018 3:30 PM EDT
Title: Some problems on the size Ramsey numbers
| Speaker: | Gholam Reza Omidi |
| Affiliation: | Isfahan University of Technology |
| Room: | MC 5417 |
Abstract: For given simple graphs $G_1$ and $G_2$, the size Ramsey number $\hat{R}(G_1,G_2)$ is the smallest positive integer $m$,
Thursday, October 25, 2018 1:30 PM EDT
Title: Maximum Independent Sets in Erdos-Ko-Rado Combinatorics
| Speaker: | Nathan Lindzey |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract: We discuss a general algebraic method for characterizing maximum independent sets in graphs that arise in Erdos-Ko-Rado combinatorics, provided the graphs are large enough.
Friday, October 19, 2018 3:30 PM EDT
Title: New algorithms for maximum disjoint paths based on tree-likeness
| Speaker: | Matthias Mnich |
| Affiliation: | University of Bonn |
| Room: | MC 5501 |
Abstract:
We study the classical NP-hard problems of finding maximum-size subsets from given sets of k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph.
Friday, October 19, 2018 1:00 PM EDT
Title: Primal-dual and Lagrangian relaxation techniques for k-median
| Speaker: | Madison Van Dyk |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract: We will develop primal-dual algorithms to obtain constant-factor approximations for the uncapacitated facility location problem.
Thursday, October 18, 2018 3:30 PM EDT
Title: Extending Thomassen’s Theorem to Two Faces
| Speaker: | Joshua Nevin |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
Let G be a planar graph and let L be a list-assignment for G in which there is a precolored edge on the outer face, every other vertex on the outer face has a list of size at least 3, and every other vertex in G has a list of size at least 5.
Thursday, October 18, 2018 1:30 PM EDT
Title: Graphs of Homomorphisms
| Speaker: | Chris Godsil |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract: If X and Y are graphs and f is a function on V (X) taking values in V (Y ), then the graph of
f is the subset formed by the pairs (x; f(x)) for x in V (X).
Wednesday, October 17, 2018 4:00 PM EDT
Title: Tutorial on back-propagation and automatic differentiation
| Speaker: | Steve Vavasis |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract: In this presentation, I'll cover the basics of automatic differentiation (AD).
Wednesday, October 17, 2018 3:30 PM EDT
Title: Basis Shape Loci and the Positive Grassmannian
| Speaker: | Cameron Marcot |
| Affiliation: | University of Waterloo |
| Room: | MC 6483 |
Abstract: We study the set of k-dimensional planes in R^n admitting a basis of vectors with prescribed supports.
Friday, October 12, 2018 10:30 AM EDT
Title: Offline Assisted Group Key Exchange
| Speaker: | Gareth Davies |
| Affiliation: | Norwegian University of Science and Technology (NTNU) |
| Room: | MC 5417 |
Abstract:
This talk will focus on the problem of forward secrecy in group key exchange (GKE), where most of the participants remain offline until they wish to compute the key.
Thursday, October 4, 2018 3:30 PM EDT
Title: Representable orientable matroids that are not real-representable
| Speaker: | Rutger Campbell |
| Affiliation: | University of Waterllo |
| Room: | MC 5417 |
Abstract: In this talk we will have a brief introduction to oriented matroids and their relation to real-representability.
Thursday, October 4, 2018 1:30 PM EDT
Title: Controllable graphs
| Speaker: | Chris Godsil |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract: A graph is controllable if no eigenvector is orthogonal to the all-ones vector.
Wednesday, October 3, 2018 4:00 PM EDT
Title: Review of martingale theory, stochastic gradient descent, and adaptive line-line-search for stochastic optimization.
| Speaker: | Courtney Paquette |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract: With the rise of large data sets, practical algorithms for machine learning often use probability and statistics.