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 9, 2022 — 12:00 PM EST
Title: Approximation algorithm for stochastic k-TSP
| Speaker: | David Aleman |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 or contact Rian Neogi for Zoom link |
Abstract: The input of the deterministic k-TSP problem consists of a metric complete graph with root p in which the nodes are assigned a fixed non-negative reward. The objective is to construct a p-rooted path of minimum length that collects total reward at least k. In this talk we will explore a stochastic variant of this problem in which the rewards assigned to the nodes are independent random variables, and the objective is to derive a policy that minimizes the expected length of a p-rooted path that collects total reward at least k. We will discuss approximation algorithms for this problem proposed in a paper by Ene, Nagarajan and Saket, and a paper by Jiang, Li, Liu and Singla.
Friday, December 9, 2022 — 3:30 PM EST
Titile: Global geometric reductions for some bottleneck questions in hardness of approximation
| Speaker: | Vijay Bhattiprolu |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 or contact Eva Lee for Zoom link |
Abstract: I will describe the classical "local gadget reduction" paradigm for proving hardness of approximation results and then list some important optimization problems that resist all such attacks. With a focus on problems that can be cast as quadratic maximization over convex sets, I will describe some successes in bypassing the aforementioned bottleneck using ideas from geometry. Time permitting I will also describe some compelling new frontiers where answering some questions in convex geometry could be the path forward.
Friday, December 16, 2022 — 3:30 PM EST
Title: Probabilistic root finding in code-based cryptography
| Speaker: | Daniel Panario |
| Affiliation: | School of Mathematics and Statistics, Carleton University |
| Location: | MC 5501 or contact Eva Lee for Zoom link |
Abstract: Factorization of polynomials over finite fields, and the particular subproblem of finding roots of polynomials, have many applications in diverse areas such as computer algebra, cryptography and coding theory, among many others. In practice, fast factorization algorithms are probabilistic.