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: Sublinear Regret 101
Speaker: | Nathan Benedetto Proenca |
Affiliation: | University of Waterloo |
Location: | MC 6029 |
Abstract: The purpose of this talk is to look at specific algorithms for online convex optimization attaining sublinear regret. In this way, we can get more familiar with the online learning setup and with the ingredients necessary to attain sublinear regret.
Title: Wires, bits, and the cost of sorting
Speaker: | Samuel Jaques |
Affiliation: | University of Waterloo |
Location: | MC 5501 |
Abstract: How hard is it to sort a list of n integers? A basic course on algorithms says it's O(n log n) time, but what if the list is enormous - so big you would need to cover the surface of the moon just to store it?
Title: A threshold for fractional Sudoku completion
Speaker: | Peter Dukes |
Affiliation: | University of Victoria |
Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: The popular puzzle game Sudoku presents a player with a 9-by-9 grid having some numbers filled in a few of the cells. The player must finish filling in numbers from 1 to 9 so that every row, column, and 3-by-3 box contains each of these numbers exactly once. We can extend Sudoku so that the boxes are $h$-by-$w$, and the overall array is $n$-by-$n$, where $n=hw$. The puzzle is now similar to completing a latin square of order n, except of course that Sudoku has an additional box condition.
Title: The Container method for Enumerating Triangle-free graphs
Speaker: | Amitha Vallapuram |
Affiliation: | University of Waterloo |
Location: | MC 5417 |
Abstract: The container method is a tool for bounding the number of independent sets in graphs and can be generalized to hypergraphs. It utilizes the observation that independent sets are found in clusters or “containers” within the graph. One application of this method is to bound the number of finite objects with some forbidden substructure. For example, we can bound the number of graphs on N vertices that do not contain K3 as a subgraph, that is, the number of Triangle-free graphs on N vertices. We will take a look at finding this bound using the container method.
Title: Prophets, philosophers, and online algorithms
Speaker: | David Wajc |
Affiliation: | Technion |
Location: | MC 6029 |
Abstract: In online Bayesian selection problems, a seller is faced with a stream of buyers arriving sequentially. Each arriving buyer makes, for each item on sale, a take-it-or-leave-it offer drawn from some known distribution, which the seller must immediately either accept or decline. It is common to compare the seller's benefit to the optimal offline solution, obtained by a "prophet'' who knows the future. However, the seller might not even be able to compete with the optimal online algorithm, which may be computationally intractable to run. In this case the optimal online algorithm is obtained by a "philosopher'' with sufficient time to think (compute). In this talk I will discuss some developments on online algorithms efficiently approximating this philosopher.
Title: Nash-Williams Orientation for Infinite Graphs
Speaker: | Amena Assem Abd-AlQader Mahmoud |
Affiliation: | University of Waterloo |
Location: | MC 5501 |
Abstract: Nash-Williams proved in 1960 that an edge-connectivity of 2k is sufficient for a finite graph to admit a k-arc-connected orientation and conjectured that the same holds for infinite graphs. We show that the conjecture is true for locally finite graphs with countably many ends.
This is joint work with Max Pitz and Marcel Koloschin.
Title: Online edge colouring
Speaker: | David Wajc |
Affiliation: | Technion — Israel Institute of Technology |
Location: | MC 5501 |
Abstract: Vizing's Theorem provides an algorithm that edge colors any graph of maximum degree Δ can be edge-colored using Δ+1 colors, which is necessary for some graphs, and at most one higher than necessary for any graph. In online settings, the trivial greedy algorithm requires 2Δ-1 colors, and Bar-Noy, Motwani and Naor in the early 90s showed that this is best possible, at least in the low-degree regime.
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.