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!
![](/combinatorics-and-optimization/sites/default/files/uploads/images/math_and_computer_building_tie.jpg)
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
Tutte Colloquium - Carla Groenland
Title: Tight bounds for reconstructing graphs from distance queries
Speaker: | Carla Groenland |
Affiliation: | TU Delft |
Location: | MC 5501 |
Abstract: Suppose you are given the vertex set of a graph and you want to discover the edge set. An oracle can tell you, given two vertices, what the distance is between these vertices in the graph. (For example, in a computer network, this would represent the minimum number of communication links needed to send a message from one computer to another.) Based on the answer, you may select the next query. The (labelled) graph is reconstructed when there is a single edge set compatible with the answers. How many queries are needed, in the worst case? The question becomes interesting for bounded degree graphs. We provide tight bounds for various classes of graphs, improving both the lower and upper bound, in both the randomized and deterministic setting.
Algebraic Graph Theory - Cristina Dalfó
Title: The spectra of lift and factored lifts of graphs or digraphs
Speaker: |
Cristina Dalfó |
Affiliation: | Universitat de Lleida |
Location: | Please contact Sabrina Lato for the Zoom link. |
Abstract: In this talk, we first explain the path we took from defining polynomial matrices to a generalization of voltage graphs that we call combined voltage graphs. Moreover, we give a general definition of a matrix associated with a combined voltage graph, which allows us to provide a new method for computing the eigenvalues and eigenspaces of such graphs.
C&O Reading Group - Prashant Gokhale
Title: NC algorithm to find perfect matching in planar graphs
Speaker: | Prashant Gokhale |
Affiliation: | University of Waterloo |
Location: | MC 6029 |
Abstract: Is perfect matching in NC? That is, is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in theoretical computer science for over three decades, ever since the discovery of RNC matching algorithms. Within this question, the case of planar graphs has remained an enigma: On the one hand, counting the number of perfect matchings is far harder than finding one (the former is #P-complete and the latter is in P), and on the other, for planar graphs, counting has long been known to be in NC whereas finding one has resisted a solution.