Complexity

The Algorithms and Complexity group is recruiting postdoctoral researchers in theoretical computer science for autumn 2027. Candidates from all areas of theoretical computer science are invited. Apply by January 31, 2027 using the email application instructions on the official group page, supplying a CV, research statement and three recommendation letters. The group sits within Waterloo’s School of Computer Science and Faculty of Mathematics.

Thomas Schuster uses quantum-information dynamics to study complexity in increasingly coherent experimental systems. A classical polynomial-time algorithm for circuits with uncorrected noise establishes limits on their possible quantum advantage. A second result shows that universal random-matrix behaviour can emerge exponentially faster than previously expected in local circuits and time evolution, with implications for benchmarking, cryptographic protocols and fundamental physics.