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 Graph Theory-Tom Wong
Title: Quantum Search with the Signless Laplacian
| Speaker: |
Tom Wong |
| Affiliation: |
Creighton University |
| Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: Continuous-time quantum walks are typically effected by either the discrete Laplacian or the adjacency matrix. In this paper, we explore a third option: the signless Laplacian, which has applications in algebraic graph theory and may arise in layered antiferromagnetic materials. We explore spatial search on the complete bipartite graph, which is generally irregular and breaks the equivalence of the three quantum walks for regular graphs, and where the search oracle breaks the equivalence of the Laplacian and signless Laplacian quantum walks on bipartite graphs without the oracle. We prove that a uniform superposition over all the vertices of the graph partially evolves to the marked vertices in one partite set, with the choice of set depending on the jumping rate of the quantum walk. We boost this success probability to 1 by proving that a particular non-uniform initial state completely evolves to the marked vertices in one partite set, again depending on the jumping rate. For some parameter regimes, the signless Laplacian yields the fastest search algorithm of the three, suggesting that it could be a new tool for developing faster quantum algorithms.
This is joint work with Molly McLaughlin.
C&O Reading Group -David Aleman Espinosa
Title: Price of information in combinatorial optimization
| Speaker: | David Aleman Espinosa |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: Pandora's box is a classical example of a combinatorial optimization problem in which the input is uncertain and can only be revealed to us after paying probing prices.
In this problem we are given a set of n items, where each i ∈ [n] has a deterministic probing price pi ∈ R+ and a random cost Ci ∈ R+. The cost Ci is only revealed after the probing price pi is paid. The goal is to adaptively probe a subset of items S ⊆ [n] and select a probed item in order to minimize the expected selection cost plus probing price: E[min_{i∈S} Ci + ∑_{i∈S} pi]. It is well known that if the costs are independent then the problem admits an efficient and simple optimal policy.
In this talk we discuss a paper by Sahil Singla that studies a generalization of this model to more general combinatorial optimization problems such as matching, set cover and facility location.