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
Sina Kalantarzadeh wins Governor General's Gold Medal
The Governor General’s Gold Medal is one of the highest student honours awarded by the University of Waterloo.
Two 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.
Laura Pierson wins Governor General's Gold Medal
The Governor General’s Gold Medal is one of the highest student honours awarded by the University of Waterloo.
Events
Algebraic and Enumerative combinatorics seminar - Theodore Morrison-Satisfiability thresholds of linear equations over a commutative ring
| Speaker: | Theodore Morrison |
| Affiliation: | University of Waterloo |
| Location: | MC 5479 |
Abstract:The satisfiability threshold of a random constraint satisfaction problem (CSP) is the density of constraints at which a random CSP instance transitions from being satisfiable to unsatisfiable with high probability. Much of the research on well known CSPs, including the $k$-SAT problem, $k$-XORSAT problem, hypergraph colouring, and systems of linear equations, has focused on determining satisfiability thresholds.
In this talk we consider systems of linear equations over finite commutative rings as CSPs, and build on the work of Ayre, Coja-Oghlan, Gao, and Müller, who determined the satisfiability threshold for random linear equations over a finite field. We determine when the satisfiability threshold is linear in the number of variables, and show that any linear threshold over a principal ideal ring coincides with the (unique) linear threshold over fields. We also determine the satisfiability threshold for some examples of non-principal ideal rings.
This is joint work with Jane Gao.
There will be a pre-seminar presenting relevant background at beginning graduate level starting at 1:30pm in MC 5417.
Crypto Reading Group - Roman Langrehr & Sam Jaques-Information Set Decoding
Abstract: In this session, we study information set decoding (ISD), one of the main generic approaches for attacking code-based cryptosystems. We will present the basic ideas behind Prange's algorithm and Stern's algorithm, together with the general philosophy of decoding attacks in the random-code setting. The aim is to understand both the algorithmic framework and its importance in concrete security estimates.
|
CombOpt ReadingGroup - David Aleman-Unsplittable multicommodity flows in fully planar instances
Abstract: The multicommodity flow problem involves routing multiple distinct commodities through a shared network. An instance is given by an undirected graph G=(V, E(G) ) with edge capacities, and a collection of source-sink pairs (s_i,t_i) in V with associated nonnegative demands d(s_i, t_i). It will be convenient to think of the source-sink pairs as forming the edges of a demand graph H=( V, E(H) ). A flow is feasible if it routes all demands without exceeding the edge capacities, and it is unsplittable if it routes each demand along a single path. Let C be the smallest value such that the existence of a feasible flow implies the existence of an unsplittable flow that exceeds the edge capacities by at most an additivie amount of C times the maximum demand value.
We show that if G+H = (V, E(G) U E(H) ) is planar, then 1.5<= C <= 2.
Joint work with Kumar, Poremba, and Shepherd.
|