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-Vishal Gupta
Title: Minimum spectral radius in a given class of graphs
Speaker: | Vishal Gupta |
Affiliation: | University of Delaware |
Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: : In 1986, Brualdi and Solheid posed the question of determining the maximum and minimum spectral radius of a graph within a given class of simple graphs. Since then, this problem has been extensively studied for various graph classes. In this talk, I will discuss two such classes: simple connected graphs with a given order and size, and simple connected graphs with a given order and dissociation number. This presentation is based on joint works with Sebastian Cioaba, Dheer Noal Desai, and Celso Marques.
C&O Reading Group - Mahtab Alghasi
Title: A constant factor approximation for Nash social welfare with subadditive valuations, Part II
Speaker: | Mahtab Alghasi |
Affiliation: | University of Waterloo |
Location: | MC 6029 |
Abstract::Social welfare refers to a class of optimization problems where the goal is to allocate subsets of resources $\mathcal{I}$ among agents $\mathcal{A}$ (or people) such that maximizes the overall "happiness" of society in a fair and efficient manner. More specifically, each agent $i \in \mathcal{I}$ has an intrinsic \emph{valuation} function $v_i: 2^{\mathcal{I}}\rightarrow \mathbb{R}$, which is a monotone function with $v_i(\emptyset)=0$, and $v_i$ quantifies the intrinsic value for subsets of items $S\subseteq \mathcal{I}$.
Variations of allocation with different valuation and objective functions has been studied in different areas of computer science, economies, and game theory. In this talk we focus on the Nash social welfare welfare (NSW) problem; given an allocation $\mathcal{S}= (S_i)_{i\in \mathcal{A}}$ the goal is to maximize the geometric mean of agents valuations.
Unfortunately, Nash social welfare problem is NP-hard already in the case of two agents with identical additive valuations, and it is NP-hard to approximate within a factor better than 0.936 for additive valuations and $(1-\frac{1}{e})$ for submodular valuation.
Moreover, the current best approximation factors of $\simeq 0.992$ for additive valuations and $(\frac{1}{4}-\epsilon)$ for submodular valuations were found by Barman et al (2018) and Garg et al. (2023), respectively.
In this talk, we present a sketch of the algorithm in recent work by Dobzinski et al., which proves the first constant-factor approximation algorithm (with a fairly large constant $\sim \frac{1}{375,000}$) for NSW problem with subadditive valuations accessible via demand queries.
Graphs and Matroids - Sepehr
Title: The pathwidth theorem for induced subgraphs
Speaker: | Sepehr |
Affiliation: | University of Waterloo |
Location: | MC 5417 |
Abstract: We present a full characterization of the unavoidable induced subgraphs of graphs with large pathwidth. This consists of two results. The first result says that for every forest H, every graph of sufficiently large pathwidth contains either a large complete subgraph, a large complete bipartite induced minor, or an induced minor isomorphic to H. The second result describes the unavoidable induced subgraphs of graphs with a large complete bipartite induced minor. If time permits , we will also try to discuss the proof of the first result mentioned above.
Based on joint work with Maria Chudnovsky and Sophie Spirkl.