University of Waterloo

The study of the design, analysis, and implementation of algorithms is at the heart of computer science. It is difficult to envision any large scale computer application, such as an operating system, compiler, large-scale database system or computer graphics package that does not rely on the use of effective algorithms and data structures.

Researchers in our group explore a variety of algorithm types and areas of application. Applications include computational geometry, graph theory (including graph drawing), bioinformatics (see their separate entry), learning theory, network routing, search engines, database systems, quantum computing, number theory and formal languages. Approaches include the study of randomized algorithms, adaptive techniques, approximation algorithms, fixed-parameter tractable algorithms and the mathematical analysis of the performance of algorithms, as well as issues of implementation. The organization and structuring of data, fundamental to the performance of most algorithms, is a major area of study.

Computational complexity is the study of the inherent limits of efficient computation measured in terms of time, space, and other resources such as randomness. Our group includes researchers in various aspects of complexity theory including Kolmogorov complexity, as well as cryptography.

Computational and Statistical Learning Theory

Applications of Statistical Learning to Data Mining, Sensor Networks, Approximation Algorithms and Processor Architecture

Classical and quantum complexity theory

Algorithms, especially for Graph Drawing, Computational Geometry, and Planar Graphs

Sublinear-time algorithms

Complexity of Boolean functions

Bioinformatics

Music Information Retrieval

Concurrent data structures

Lock-freedom

Non-uniform memory architectures

Non-volatile memory

Transactional memory

Computational complexity

Models of feasible computation

Quantum algorithms and complexity theory

Quantum information theory

Quantum communication complexity

Statistics

Machine learning

Data privacy

Natural Computation

Bioinformation and biocomputation - theoretical aspects

Nanocomputation by DNA self-assembly

Models of cellular computation

Watson-Crick complementarity in formal languages and automata theory

Algorithmic graph theory

Approximation algorithms

Spectral graph theory

Bioinformatics

Kolmogorov complexity

Computational geometry

Graph drawing

Graph algorithms

Combinatorial optimization

Algorithms

Bioinformatics

Data structures, particularly fast and space efficient structures

The design, analysis and implementation of algorithms

Bioinformatics

Database systems and data warehousing, particularly efficiency issues

Algorithm design and analysis

Graph algorithms

Fixed-parameter tractability

Reconfiguration problems

Complexity theory

Coding theory

Combinatorics

Algebraic geometry and invariant theory

Design and analysis of algorithms

Graph-theoretic algorithms

Fixed-parameter tractable algorithms and parameterized complexity

Combinatorics on words

Formal languages and automata theory (especially connections with number theory)

Algorithmic number theory (primality testing, factoring, etc.)

History of mathematics and computer science

Ethical use of computers

Quantum complexity theory

Quantum information theory

Graph and network algorithms

Combinatorial optimization

Symbolic mathematical computation

Sparse polynomials and polynomial computation

Algebraic complexity

Approximation Algorithms

Algorithmic Game Theory

Combinatorial Optimization

Quantum information processing capacities of abstract or physical resources

Cryptographic applications of quantum information

Quantum computation by measurements only

Elliptic curve cryptography

Key establishment protocols

Practice-oriented provable security

Algorithmic number theory

Quantum Computer Algorithms

Quantum Cryptography and Communication

NMR implementations of Quantum Computer Algorithms

Cryptography

Discrete logarithm problem

Combinatorics

Quantum Computation and Quantum Information

Computational Complexity

Design and Analysis of Algorithms

Symbolic and Exact Linear Algebra

Algorithmic Number Theory

Combinatorial optimization

Approximation algorithms

Network design

Stochastic optimization

Algorithmic game theory

Scheduling

Online algorithms

Cryptography

Public-key cryptosystems

Discrete logarithm problem

Elliptic and hyperelliptic curves

Complexity issues in continuous optimization

Convex optimization and its application to data mining

Efficient algorithms for optimization

Linear algebra problems arising in optimization

Ph.D. Candidates

Supervisor: Lap Chi Lau

Supervisor: Lila Kari

Supervisor: Lila Kari

Supervisor: Eric Blais

Supervisor: Ian Munro

Supervisor: Jeffrey Shallit

Supervisor: Jonathan Buss

Supervisors: Ian Munro and Naomi Nishimura

Supervisor: Eric Blais

Supervisor: Trevor Brown and Peter Buhr

Supervisor: Eric Blais

Supervisor: Richard Cleve

Supervisor: John Watrous

Supervisors: Anna Lubiw

Supervisor: Lap Chi Lau

Supervisor: John Watrous

Supervisor: Ian Munro

Supervisor: Trevor Brown and Peter Buhr

Supervisor: Naomi Nishimura

Supervisor: Lap Chi Lau

Supervisor: Lila Kari

Supervisor: Lap Chi Lau

M.Math. Candidates

Supervisor: Jeffrey Shallit

Supervisor: Therese Biedl

Supervisor: Eric Blais

Supervisor: Jeffrey Shallit

Supervisor: Trevor Brown

Supervisors: Therese Biedl and Anna Lubiw

Supervisors: Eric Blais / Ian Munro

Supervisor: Trevor Brown

Supervisor: Anna Lubiw

Supervisor: Ian Munro

Supervisor: Ian Munro

Supervisor: Ian Munro

Ph.D. Graduates

Supervisor: Timothy Chan

Thesis title: Shortest Paths in Geometric Intersection Graphs

Supervisor: Ian Munro

Thesis title: Space Efficient Data Structures and Algorithms in the Word-RAM Model

Supervisor: Anna Lubiw

Thesis title: Straight Line Movement in Morphing and Pursuit Evasion

Supervisor: Therese Biedl

Thesis title: Restricted string representations

Supervisor: Ian Munro

Thesis title: In-Memory Storage for Labeled Tree-Structured Data

Supervisor: Alex Lopez-Ortiz

Thesis title: Generalized Set and Graph Packing Problems

Supervisor: John Watrous

Thesis title: Quantum State Local Distinguishability via Convex Optimization

Supervisor: Naomi Nishimura

Thesis title: On Reconfiguration Problems: Structure and Tractability

Supervisor: Anna Lubiw

Thesis title: Reconfiguring Triangulations

Supervisor: Alex Lopez-Ortiz

Thesis title: Alternative Approaches for Analysis of Bin Packing and List Update Problems

Supervisor: John Watrous

Thesis title: Efficient Algorithms in Quantum Query Complexity

Supervisor: John Watrous

Thesis title: Lower Bounds on Quantum Query and Learning Graph Complexities

Supervisor: Alex Lopez-Ortiz

Thesis title: Efficient Evaluation of Set Expressions

Supervisor: Naomi Nishimura

Thesis title: Parameterized Enumeration of Neighbor Strings and Kemeny Aggregations

Supervisor: Alex Lopez-Ortiz

Thesis title: Models for Parallel Computation in Multi-Core, Heterogeneous, and Ultra Wide-Word Architectures

Supervisor: Alex Lopez-Ortiz

Thesis title: Algorithms for Geometric Covering and Piercing Problems

Supervisor: Anna Lubiw

Thesis title: Simultaneous Graph Representation Problems

Supervisors: Daniel Brown and Prabhakar Ragde

Thesis title: Combinatorial and Probabilistic Approaches to Motif Recognition

Supervisor: Daniel Brown

Thesis title: Improvements in the Accuracy of Pairwise Genomic Alignment

Supervisor: Alex Lopez-Ortiz

Thesis title: Alternative Measures for the Analysis of Online Algorithms

Supervisor: John Watrous

Thesis title: Quantum Strategies and Local Operations

Supervisor: Ian Munro

Thesis title: Succinct Representation of Trees and Graphs

Supervisor: Anna Lubiw

Thesis title: Constrained Shortest Paths in Terrains and Graphs

Supervisor: John Watrous

Thesis title: Computational Distinguishability of Quantum Channels

Supervisor: Jeffrey Shallit

Thesis title: The Frobenius Problems in a Free Monoid

Supervisor: Douglas Stinson

Thesis title: Cryptographic Protocols, Sensor Network Key Management, and RFID Authentication

Supervisor: Shai Ben-David

Thesis title: Contribution to Unsupervised and Semi-Supervised Learning

Supervisor: Timothy Chan

Thesis title: Solving Geometric Problems in Space-Conscious Models

Supervisor: Timothy Chan

Thesis title: Geometric Approximation Algorithms in the Online and Data Stream Models

Supervisor: Timothy Chan

Thesis title: On Geometric Range Searching, Approximate Counting and Depth Problems

Supervisor: Jeffrey Shallit

Thesis title: Error Detection in Number-Theoretic and Algebraic Algorithms

Supervisor: Ian Munro

Thesis title: Aspects of Metric Spaces in Computation

Supervisor: Jeffrey Shallit

Thesis title: Critical Exponents and Stabilizers of Infinite Words

Supervisor: Therese Biedl

Thesis title: Reconstruction of Orthogonal Polyhedra

Supervisor: Ian Munro

Thesis title: Succinct Indexes

Supervisors: Ian Munro and Prabhakar Ragde

Thesis title: Upper and Lower Bounds for Text Indexing Data Structures

Supervisor: Naomi Nishimura

Thesis title: Intersperse Coloring

Supervisors: Therese Biedl and Anna Lubiw

Thesis title: Morphing Parallel Graph Drawings

Supervisor: Jonathan Buss

Thesis title: Characterizing Hardness in Parameterized Complexity

Supervisors: Douglas Stinson and Mark Giesbrecht

Thesis title: On the Security of Some Variants of RSA

Supervisor: Alex Lopez-Ortiz

Thesis title: Efficient Propagators for Global Constraints

Supervisors: Ming Li and Daniel Brown

Thesis title: Evidence Combination in Hidden Markov Models for Gene Prediction

Supervisors: Therese Biedl and Alex Lopez-Ortiz

Thesis title: Reconstruction and Visualization of Polyhedra Using Projections

Supervisors: Ming Li and Daniel Brown

Thesis title: Enhancements to Hidden Markov Models for Gene Finding and Other Biological Applications

Supervisor: Jeffrey Shallit

Thesis title: Periodicity and repetition in combinatorics on words

Supervisors: Anna Lubiw and Ian Munro

Thesis title: Folding and Unfolding

Supervisor: Naomi Nishimura

Thesis title: Pattern Matching in Directed Graphs

M.Math. Graduates

Supervisor: Eric Blais and Semih Salihoglu

Thesis title: Domain Ordering and Box Cover Problems for Beyond Worst-Case Join Processing

Supervisors: Ian Munro and Semih Salihoglu

Thesis title: Majority in the Three-Way Comparison Model

Supervisor: Therese Biedl

Thesis title: Bounds on Maximum Matchings in 1-Planar Graphs

Supervisor: Jeffrey Shallit

Thesis title: Powers and anti-powers in binary words

Supervisor: Jeffrey Shallit

Thesis title: Counting, Adding, and Regular Languages

Supervisor: Jeffrey Shallit

Thesis title: Using Automata Theory to Solve Problems in Additive Number Theory

Supervisor: Anna Lubiw

Thesis title: Minimum Shared-Power Edge Cut

Supervisor: Lap Chi Lau

Thesis title: The Complexity of Network Design for s-t Effective Resistance

Supervisor: John Watrous

Thesis title: Concentration Bounds from Parallel Repetition Theorems

Supervisor: Ian Munro

Thesis title: Efficient Representation and Encoding of Distributive Lattices

Supervisor: Eric Blais

Thesis title: Halfway to halfspace testing

Supervisor: Eric Blais

Thesis title: Testing submodularity

Supervisor: Alex Lopex-Ortiz, Ian Munro

Thesis title: Performance of the Ultra-Wide Word Model

Supervisor: Naomi Nishimura

Thesis title: Reconfiguring Graph Colourings

Supervisor: Jeffrey Shallit

Thesis title: Discriminators of Integer Sequences

Supervisor: Anna Lubiw

Thesis title: A Faster Algorithm for Recognizing Edge-Weighted Interval Graphs

Supervisor: Jeffrey Shallit

Thesis title: Properties of Two-Dimensional Words

Supervisor: Naomi Nishimura

Thesis title: Graph Editing to a Given Neighbourhood Degree List is Fixed-Parameter Tractable

Supervisors: Therese Biedl and Timothy Chan

Thesis title: Upward Octagonal Drawings of Ternary Trees

Supervisors: Timothy Chan

Thesis title: Three Approaches to Building Time-Windowed Geometric Data Structures

Supervisors: Therese Biedl

Thesis title: A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings

Supervisors: Alex Lopez-Ortiz and Ian Munro

Thesis title: Optimal Path-Decomposition of Tries

Supervisors: Ian Munro

Thesis title: Approximately Optimum Search Trees in External Memory Models

Supervisors: Ian Munro

Thesis title: Towards the Efficient Generation of Gray Codes in the Bitprobe Model

Supervisors: Therese Biedl and Sebastian Fischmeister

Thesis title: Graph-theoretic Properties of Control Flow Graphs and Applications

Supervisor: Ian Munro

Thesis title: Inverting Permutations In Place

Supervisor: Naomi Nishimura

Thesis title: On the Complexity of Reconfiguration of Clique, Cluster Vertex Deletion, and Dominating Set

Supervisor: John Watrous

Thesis title: Optimal Success Bounds for Single Query Quantum Algorithms Computing the General SUM Problem

Supervisor: Ian Munro

Thesis title: On the Succinct Representation of Equivalence Classes

Supervisor: Anna Lubiw

Thesis title: The Star Unfolding from a Geodesic Curve

Supervisor: Therese Biedl

Thesis title: Planar Open Rectangle-of-Influence Drawings

Supervisor: Jeffrey Shallit

Thesis title: Variations on the Erdos Discrepancy Problem

Supervisor: Ian Munro

Thesis title: Exploiting the Computational Power of Ternary Content Addressable Memory

Supervisor: Timothy Chan

Thesis title: Streaming and Dynamic Algorithms for Minimum Enclosing Balls in High Dimensions

Supervisor: Therese Biedl

Thesis title: The Vulcan game of Kal-toh: Finding or making triconnected planar subgraphs

Supervisor: Alex Lopez-Ortiz

Thesis title: Geometric On-line Ray Searching Under Probability of Placement Scenarios

Supervisor: Therese Biedl

Thesis title: Drawing planar graphs with prescribed face areas

Supervisor: Ian Munro

Thesis title: Simultaneously Embedding Planar Graphs at Fixed Vertex Locations

Supervisor: Jeffrey Shallit

Thesis title: Problems Related to Shortest Strings in Formal Languages

Supervisor: Ian Munro

Thesis title: Distributed Policing with Full Utilization and Rate Guarantees

Supervisor: Therese Biedl

Thesis title: Reconstructing hv-convex polyominoes with multiple colours

Supervisor: Ian Munro

Thesis title: The application of the in-tree knapsack problem to routing prefix caches

Supervisor: Anna Lubiw

Thesis title: The Steiner ratio for the obstacle-avoiding Steiner tree problem

Supervisor: Anna Lubiw

Thesis title: Algorithms for Optimizing Search Schedules in a Polygon

Supervisor: Anna Lubiw

Thesis title: Packing Unit Disks

Supervisors: Naomi Nishimura and Kate Larson

Thesis title: Representations and Parameterizations of Combinatorial Auctions

Supervisor: Jeremy Barbay

Thesis title: Adaptive Algorithms for Weighted Queries on Weighted Binary Relations and Labeled Trees

Supervisor: Jonathan Buss

Thesis title: Cache Considerations in Algorithm Design

Supervisor: Naomi Nishimura

Thesis title: A New Optimality Measure for Distance Dominating Sets

Supervisor: Timothy Chan

Thesis title: Approximation Algorithms for Rectangle Piercing Problem

Supervisor: Douglas Stinson

Thesis title: Unconditionally Secure Authentication Codes and Digital Signatures

Supervisor: Ian Munro

Thesis title: Improved Searching in the Presence of Permanent Faults

Supervisor: Daniel Brown

Thesis title: Haplotype inference using pure parsimony

Supervisor: Therese Biedl

Thesis title: Planar Graphs and Partial k-Trees

Supervisor: Anna Lubiw

Thesis title: A Geometric Approach to Pattern Matching in Polyphonic Music

Supervisor: Douglas Stinson

Thesis title: Algorithms for Detecting Cheaters in Threshold Schemes

Supervisor: Naomi Nishimura

Thesis title: Ordered Interval Routing Schemes

Supervisor: Therese Biedl

Thesis title: Hexagonal Grid Drawings

Supervisor: Daniel Brown

Thesis title: New anchoring techniques for global multiple alignment of genomic sequences

Supervisor: Jeffrey Shallit

Thesis title: Monoids and the state complexity of root(L)

Supervisor: Timothy Chan

Thesis title: Towards In-Place Algorithms in Computational Geometry

Supervisor: Ian Munro

Thesis title: Cache-Oblivious Searching and Sorting In Multisets

Supervisor: Daniel Brown

Thesis title: A Combinatorial Approach for Motif Discovery in Unaligned DNA Sequences

Supervisors: Naomi Nishimura and Prabhakar Ragde

Thesis title: Updating the Vertex Separation of a Dynamically Changing Tree

Supervisor: Jeffrey Shallit

Thesis title: Infinite Sequences and Pattern Avoidance

Supervisor: Naomi Nishimura

Thesis title: Adaptive Comparison-Based Algorithms for Evaluating Set Queries

Supervisor: Timothy Chan

Thesis title: Geometric Optimization Problems over Sliding Windows and Similarity Search in Metric Spaces

Supervisor: Daniel Brown

Thesis title: Incoporating Spaced Seeds into PSI-BLAST Search

Supervisor: Naomi Nishimura

Thesis title: A Parameterized Algorithm for Upward Planarity Testing of Biconnected Graphs

Supervisor: Jeffrey Shallit

Thesis title: Descriptional Complexity Measures of Regular Languages

Supervisor: Jeffrey Shallit

Thesis title: Grey Level Visual Cryptography for General Access Structures

Supervisor: Jeffrey Shallit

Thesis title: Topics in Formal Languages: String Enumeration, Unary NFA's, and State Complexity

Supervisor: Therese Biedl

Thesis title: Bounded-Degree Independent Sets in Planar Graphs

Supervisor: Jeffrey Shallit

Thesis title: Minimal covers of formal languages

Supervisor: Naomi Nishimura

Thesis title: Multi-dimensional Interval Routing Schemes

Supervisor: Naomi Nishimura

Thesis title: Algorithms for Graphs of (Locally) Bounded Treewidth

The Algorithms & Complexity group runs a weekly seminar, typically on Wednesday afternoons at 1:30pm. It is currently organized by Anurag Murty Naredla.

To receive announcements by email, subscribe to the student mailing list (for students at the University of Waterloo) or the general mailing list. To schedule a talk for the seminar, contact the organizer directly.

Winter 2019 Graduate Courses

Eric Blais

Jeffrey Shallit

Fall 2018 Graduate Courses

Anna Lubiw

Ian Munro

Shalev Ben-David

Spring 2018 Graduate Courses

Lap Chi Lau

Winter 2018 Graduate Courses

Jeffrey Shallit

Fall 2017 Graduate Courses

Eric Blais

Eric Blais

Spring 2017 Graduate Courses

Therese Biedl

Winter 2017 Graduate Courses

Lap Chi Lau

Jeffrey Shallit

John Watrous

Fall 2016 Graduate Courses

Eric Blais

Anna Lubiw

Yaoliang Yu

Ian Munro

Jonathan Buss

Winter 2016 Graduate Courses

Eric Blais

Eric Blais

Timothy Chan

Fall 2015 Graduate Courses

Bin Ma

Shai Ben-David

John Watrous

Richard Cleve

Lap Chi Lau

Spring 2015 Graduate Courses

Timothy Chan

Ming Li

Winter 2015 Graduate Courses

Fall 2014 Graduate Courses

Bin Ma

Richard Cleve

Ian Munro

Anna Lubiw

Eric Blais

John Watrous

The University of Waterloo offers a unique destination for pursuing studies in Algorithms and/or in Complexity Theory. With 17 core members in the Algorithms & Complexity group, over 70 faculty members in the School of Computer Science, and hundreds of researchers within the Faculty of Mathematics, the University of Waterloo is a unique destination for pursuing studies in Algorithms and in Complexity theory.

Interested in joining us? See here for much more information about our department and for the application instructions.

The Algorithms & Complexity group at the University of Waterloo is offering one postdoctoral position starting in the Fall of 2020. We seek candidates from all areas of theoretical computer science.

Interested applicants should have their CV, research statement, and three recommendation letters emailed to theory.waterloo@gmail.com. Applications are due December 31st. Questions about the position should be sent to the email above.

The University of Waterloo regards diversity as an integral part of academic excellence and is committed to employment equity and accessibility for all employees. As such, we encourage applications from women, Indigenous (First Nations, Métis, and Inuit) peoples, persons with disabilities, members of diverse gender identities, and others who may contribute to the further diversification of ideas.

See here for directions and contact information.