The C&O department has 36 faculty members and 60 graduate students. We are intensely research oriented and hold a strong international reputation in each of our six major areas:
- Algebraic combinatorics
- Combinatorial optimization
- Continuous optimization
- Cryptography
- Graph theory
- Quantum computing
Read more about the department's research to learn of our contributions to the world of mathematics!
News
Three C&O faculty win Outstanding Performance Awards
The awards are given each year to faculty members across the University of Waterloo who demonstrate excellence in teaching and research.
Prof. Alfred Menezes is named Fellow of the International Association for Cryptologic Research
The Fellows program, which was established in 2004, is awarded to no more than 0.25% of the IACR’s 3000 members each year and recognizes “outstanding IACR members for technical and professional contributions to cryptologic research.”
C&O student Ava Pun receives Jessie W. H. Zou Memorial Award
She received the award in recognition of her research on simulating virtual training environments for autonomous vehicles, which she conducted at the start-up Waabi.
Events
Algebraic and enumerative combinatorics seminar-Michael Borinsky
Title: Asymptotic count of edge-bicolored graphs
| Speaker | Michael Borinsky |
| Affiliation | Perimeter Institute and C&O |
| Location | MC 5479 |
Abstract: I will talk about recent joint work with Chiara Meroni and Max Wiesmann, where we showed that specific exponential bivariate integrals serve as generating functions of labeled edge-bicolored graphs. Based on this, we prove an asymptotic formula for the number of regular edge-bicolored graphs with arbitrary weights assigned to different vertex structures.
The asymptotic behavior is governed by the critical points of a polynomial. An interesting application of this purely combinatorial work to mathematical physics is the Ising model on a random graph. I will explain how its phase transitions arise from our formula.
There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,
Tutte colloquium-Arnesh Sujanani
Title:The Inexact Augmented Lagrangian Method: Optimal Complexity Bounds and Applications to Solving Huge SDPs
| Speaker: | Arnesh Sujanani |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract:In the first part of this talk, we present optimal and nearly-optimal parameter-free augmented Lagrangian (AL) methods for convex and strongly optimization with linear constraints. Our AL methods employ tractable inexact criteria for solving their inner subproblems, which accelerated methods can be shown to achieve in a finite number of iterations that depends on the target accuracy.
In the second part of this talk, we present a new inexact augmented Lagrangian method, namely, HALLaR, that employs a Burer-Monteiro style low-rank factorization for solving large-scale semidefinite programs (SDPs). The AL subproblems are solved by a hybrid low-rank method, which is based on a combination of a low-rank Frank-Wolfe method and a nonconvex accelerated inexact proximal point method. In contrast to the classical low-rank method by Burer and Monteiro, HALLaR finds a near-optimal solution (with provable complexity bounds) of SDP instances satisfying strong duality. Computational results comparing HALLaR to state-of-the-art solvers on several large SDP instances show that the former finds higher accurate solutions in substantially less CPU time than the latter ones. For example, in less than 20 minutes, HALLaR can solve (on a personal laptop) a maximum stable set SDP with 1 million vertices and 10 million edges within 1e-5 relative accuracy.
This talk is based on joint work with Saeed Ghadimi and Henry Wolkowicz from University of Waterloo and Diego Cifuentes and Renato Monteiro from Georgia Tech.