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
Laura Pierson wins Governor General's Gold Medal
The Governor General’s Gold Medal is one of the highest student honours awarded by the University of Waterloo.
Sepehr Hajebi wins Graduate Research Excellence Award, Mathematics Doctoral Prize, and finalist designation for Governor General's Gold Medal
The Mathematics Doctoral Prizes are given annually to recognize the achievement of graduating doctoral students in the Faculty of Mathematics. The Graduate Research Excellence Awards are given to students who authored or co-authored an outstanding research paper.
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.
Events
Tutte colloquium-Gary Au
Title:Worst-case instances of the stable set problem of graphs for the Lovász–Schrijver SDP hierarchy
| Speaker: | Gary Au |
| Affiliation: | University of Saskatchewan |
| Location: | MC 5501 |
Abstract:(Based on joint work with Levent Tunçel.)
In this talk, we discuss semidefinite relaxations of the stable set problem of graphs generated by the lift-and-project operator LS_+ (due to Lovász and Schrijver), and present some of our recent progress on this front. In particular, we show that for every positive integer k, the smallest graph with LS_+-rank k contains exactly 3k vertices. This result is sharp and settles a conjecture posed by Lipták and Tunçel from 2003.
The talk will be accessible to a general audience, and does not assume any prior knowledge of lift-and-project methods.
Tutte colloquium-Henry Wolkowicz
Title:The omega-Condition Number: Applications to Preconditioning and Low Rank Generalized Jacobian Updating
| Speaker: | Henry Wolkowicz |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: Preconditioning is essential in iterative methods for solving linear systems. It is also the implicit objective in updating approximations of Jacobians in optimization methods, e.g.,~in quasi-Newton methods. We study a nonclassic matrix condition number, the omega-condition number}, omega for short. omega is the ratio of: the arithmetic and geometric means of the singular values, rather than the largest and smallest for the classical kappa-condition number. The simple functions in omega allow one to exploit first order optimality conditions. We use this fact to derive explicit formulae for (i) omega-optimal low rank updating of generalized Jacobians arising in the context of nonsmooth Newton methods; and (ii) omega-optimal preconditioners of special structure for iterative methods for linear systems. In the latter context, we analyze the benefits of omega for (a) improving the clustering of eigenvalues; (b) reducing the number of iterations; and (c) estimating the actual condition of a linear system. Moreover we show strong theoretical connections between the omega-optimal preconditioners and incomplete Cholesky factorizations, and highlight the misleading effects arising from the inverse invariance of kappa. Our results confirm the efficacy of using the omega-condition number compared to the kappa-condition number.
(Joint work with: Woosuk L. Jung, David Torregrosa-Belen.)