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, December 1, 2023 1:00 PM EST
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.
Friday, December 1, 2023 3:30 PM EST
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?
Monday, December 4, 2023 11:30 AM EST
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.
Thursday, December 7, 2023 3:00 PM EST
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.
Friday, December 8, 2023 1:00 PM EST
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.
Friday, December 8, 2023 3:30 PM EST
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.
Friday, December 15, 2023 3:30 PM EST
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.