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 - Carla Groenland

**Title: **Tight bounds for reconstructing graphs from distance queries

Speaker: |
Carla Groenland |

Affiliation: |
TU Delft |

Location: |
MC 5501 |

**Abstract: **Suppose you are given the vertex set of a graph and you want to discover the edge set. An oracle can tell you, given two vertices, what the distance is between these vertices in the graph. (For example, in a computer network, this would represent the minimum number of communication links needed to send a message from one computer to another.) Based on the answer, you may select the next query. The (labelled) graph is reconstructed when there is a single edge set compatible with the answers. How many queries are needed, in the worst case? The question becomes interesting for bounded degree graphs. We provide tight bounds for various classes of graphs, improving both the lower and upper bound, in both the randomized and deterministic setting.

## Distinguished Tutte Lecture - Ryan O'Donnell

**Title: **Quartic quantum speedups for planted inference

Speaker: |
Ryan O'Donnell |

Affiliation: |
CMU |

Location: |
MC 5501 |

**Abstract: **Consider the following task ("noisy 4XOR"), arising in CSPs, optimization, and cryptography. There is a 'secret' Boolean vector x in {-1,+1}^n. One gets m randomly chosen pairs (S, b), where S is a set of 4 coordinates from [n] and b is x^S := prod_{i in S} x_i with probability 1-eps, and -x^S with probability eps. Can you tell the difference between the cases eps = 0.1 and eps = 0.5?

## Tutte Colloquium - Bruno Lourenço

**Title: **Oddities in the pursuit of self-duality

Speaker: |
Bruno Lourenço |

Affiliation |
The Institute of Statistical Mathematics |

Location: |
MC 5501 |

**Abstract: **Certain important cones in conic optimization are self-dual, e.g., the positive semidefinite matrices and the nonnegative orthant. In this talk we will address the problem of determining which convex cones are self-dual in a broad sense, which allows changing the underlying inner product if necessary. We will describe some recent progress on this question for polyhedral cones and discuss some unexpected connections. In particular, we will show a curious result connecting self-dual polyhedral cones and extreme rays of doubly nonnegative matrices. We will also discuss how semidefinite programming can be used to search for self-dual polyhedral cones. Time allowing, we will describe new results on the related problem of determining the automorphisms of certain cones of interest.

This talk is based on joint works with João Gouveia and Masaru Ito.