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
C&O Reading Group - Rian Neogi
Title: A Constant Factor Prophet Inequality for Subadditive Combinatorial Auctions
| Speaker: | Rian Neogi |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: In this talk, I will go through the paper of Correa and Cristi that appeared in STOC 2023. The paper proves a O(1) prophet inequality for online combinatorial auctions with subadditive buyers.
Their techniques involve the use of what they call a Random Score Generator (RSG for short), which is a distribution over prices of the items. Each buyer 'plays' an RSG. The algorithm samples a vector of prices of the items from this RSG for each buyer as they arrive, and assigns to them the set of items for which the sampled prices are larger than prices from another independent sample from the RSGs of all the buyers. A mirroring argument is used to bound the value of the allocation computed by their algorithm, and a novel fixed point argument is used to show the existence of RSGs that guarantee a good approximation.
In contrast to the O(log log m) prophet inequality covered previously in the CO reading group, the algorithm in this paper does not run in polynomial time, and does not involve posted prices.
Algebraic Graph Theory-Frederico Cançado
Title: Quotient graphs and stochastic matrices
| Speaker: | Frederico Cançado |
| Affiliation: | Universidade federal de Minas gerais |
| Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: Whenever graphs admit equitable partitions, their quotient graphs highlight the structure evidenced by the partition. It is therefore very natural to ask what can be said about two graphs that have the same quotient according to certain equitable partitions. This question has been connected to the theory of fractional isomorphisms and covers of graphs in well-known results that we briefly presents in these slides. We then depart to develop theory of what happens when the two graphs have the same symmetrized quotient, proving a structural result connecting this with the existence of certain doubly stochastic matrices. We apply this theorem to derive a new characterization of when two graphs have the same combinatorial quotient, and we also study graphs with weighted vertices and the related concept of pseudo-equitable partitions. Our results connect to known old and recent results, and are naturally applicable to study quantum walks.