We hope you are enjoying your time in our graduate programs. Check out our course offerings, information about degree completion, the PhD qualifying exams, the PhD lecturing requirement, and instructions on submitting your PhD annual activity report. If you still have some years ahead in your grad studies, you might be interested in applying for scholarships.
If you have any administrative questions, please contact us at cograd@uwaterloo.ca.
Seminars in Combinatorics and Optimization
Distinguished Tutte Lecture - Katya Scheinberg
Title: Stochastic Oracles and Where to Find Them
| Speaker: | Katya Scheinberg |
| Affiliation: | Cornell University |
| Location: | MC 5501 |
Abstract: Continuous optimization is a mature field, which has recently undergone major expansion and change. One of the key new directions is the development of methods that do not require exact information about the objective function. Nevertheless, the majority of these methods, from stochastic gradient descent to "zero-th order" methods use some kind of approximate first order information. We will overview different methods of obtaining this information, including simple stochastic gradient via sampling, robust gradient estimation in adversarial settings, traditional and randomized finite difference methods and more.
We will discuss what key properties of these inexact, stochastic first order oracles are useful for convergence analysis of optimization methods that use them.
C&O Special Seminar - Vijay Vazirani
Title: A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length - Part 1
| Speaker: | Vijay Vazirani |
| Affiliation: | University of California, Irvine |
| Location: | MC 5479 |
Abstract: It is well known that the proof of some prominent results in mathematics took a very long time --- decades and even centuries. The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed --- over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max-flow.
The new ideas contained in the MV algorithm and its proof remain largely unknown, and hence unexplored, for use elsewhere.
The purpose of this two-talk-sequence is to rectify that shortcoming.
C&O Special Seminar - Vijay Vazirani
Title: A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length - Part 2
| Speaker: | Vijay Vazirani |
| Affiliation: | University of California, Irvine |
| Location: | MC 5479 |
Abstract: It is well known that the proof of some prominent results in mathematics took a very long time --- decades and even centuries. The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed --- over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max-flow.
The new ideas contained in the MV algorithm and its proof remain largely unknown, and hence unexplored, for use elsewhere.
The purpose of this two-talk-sequence is to rectify that shortcoming.