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
Tutte colloquium-Stephan Pfannerer-Mittas
Title:A mystery group action and the mystery statistic
Speaker: | Stephan Pfannerer-Mittas |
Affiliation: | University of Waterloo |
Location: | MC 5501 |
Abstract: In 2010, B. Rhoades proved that promotion on rectangular standard Young tableaux together with the associated fake-degree polynomial shifted by an appropriate power, provides an instance of the cyclic sieving phenomenon.
Motivated in part by this result, we show that we can expect a cyclic sieving phenomenon for m-tuples of standard Young tableaux of the same shape and the m-th power of the associated fake-degree polynomial, for fixed m, under mild and easily checked conditions. However, we are unable to exhibit an appropriate group action explicitly.
Put differently, we determine in which cases the mth tensor power of a character of the symmetric group carries a permutation representation of the cyclic group.
To do so, we use a method proposed by N. Amini and P. Alexandersson, which amounts to establishing a bound on the number of border-strip tableaux.
Finally, we apply our results to the invariant theory of tensor powers of the adjoint representation of the general linear group. In particular, we prove the existence of a statistic on permutations, which is equidistributed with the RSK-shape and invariant under rotation.
This is based on joint work with Per Alexandersson, Martin Rubey and Joakim Uhlin.
Algebraic Graph Theory-Joannes Vermant
Title: Cayley incidence graphs
Speaker: | Joannes Vermant |
Affiliation: | Umeå University |
Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: Evra, Feigon, Maurischat, and Parzanchevksi defined Cayley incidence graphs (which they refer to as Cayley bigraphs), a class of biregular graphs used to construct bipartite expander graphs. These graphs are defined using a group G and a set of cells satisfying certain properties. Alternatively, they can be described as the incidence graphs of uniform and regular linear hypergraphs with a group G acting regularly on the vertices. In this talk, I will explore some basic properties of Cayley incidence graphs, as well as their connections to other combinatorial objects such as designs, coset geometries, and difference sets.
This talk is based on joint work with Arnbjörg Soffía Árnadóttir, Alexey Gordeev, Sabrina Lato, and Tovohery Randrianarisoa.
C&O Reading Group -Noah Weninger
Title: Complexity in linear multilevel programming
Speaker: | Noah Weninger |
Affiliation: | University of Waterloo |
Location: | MC 6029 |
Abstract:Bilevel linear programming (BLP) is a generalization of linear programming (LP) in which a subset of the variables is constrained to be optimal for a second LP, called the lower-level problem. Multilevel linear programming (MLP) extends this further by replacing the lower-level LP with a BLP or even another MLP, up to some finite number of levels. MLP can be seen as a game-theoretic extension of LP where multiple decision makers with competing interests each have control over some subset of the variables in the problem. We discuss the computational complexity of solving MLP problems, including some recent results on the complexity of determining whether MLPs are unbounded (Rodrigues, Carvalho, and Anjos 2024). We will end with an interesting open problem about the complexity of determining unboundedness for a
special case of BLP.