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-David Wagner
Title:Valuable partial orders
| Speaker | David Wagner |
| Affiliation | University of Waterloo |
| Location | MC 5479 |
Abstract: In the pre-seminar we will review Birkhoff's structure theory for finite distributive lattices and its consequences for the geometry of some algebraic varieties associated with lattices by Hibi. In the seminar itself we will look more closely at the geometry of these varieties, motivating the definition of an interesting class of partial orders and raising several open problems.
There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,
Tutte colloquium-Robert Andrews
Title: Constant-Depth Arithmetic Circuits for Linear Algebra Problems
| Speaker: | Robert Andrews |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: What is the computational complexity of the greatest common divisor (GCD) of two univariate polynomials? The Euclidean algorithm provides a polynomial-time solution, and fast variants of the Euclidean algorithm can compute the GCD in nearly-linear time. The GCD can also be expressed in a linear-algebraic form. Basic tasks in linear algebra, such as computing determinants and solving linear systems, can be performed in O(log^2 n) parallel time, and this can be used to compute the GCD in O(log^2 n) parallel time. This algorithm does not take advantage of any structure present in the resulting linear systems, so in principle one could compute the GCD in parallel even faster.
In this talk, I will describe a new algorithm that computes the GCD in O(log n) parallel time by using a combination of polynomial interpolation and Newton's identities for symmetric polynomials. In fact, this algorithm can be implemented as an arithmetic circuit of constant depth. Similar ideas yield constant-depth circuits to compute the resultant, Bézout coefficients, and squarefree decomposition.