University of Waterloo logo

Research Overview

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.

People

Shai Ben-David

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

Therese Biedl

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

Eric Blais

Sublinear-time algorithms
Complexity of Boolean functions

Daniel G. Brown

Bioinformatics
Music Information Retrieval

Jonathan Buss

Computational complexity
Models of feasible computation

Timothy M. Chan

Discrete and computational geometry
Design and analysis of algorithms

Richard E. Cleve

Quantum algorithms and complexity theory
Quantum information theory
Quantum communication complexity

Ming Li

Bioinformatics
Kolmogorov complexity

Alejandro (Alex) López-Ortiz

The Internet and the World Wide Web
Text-dominated databases/search engines
On-line Searching and Path Planning
Constraint Programming

Anna Lubiw

Computational geometry
Graph drawing
Graph algorithms
Combinatorial optimization

Bin Ma

Algorithms
Bioinformatics

J. Ian Munro

Data structures, particularly fast and space efficient structures
The design, analysis and implementation of algorithms
Bioinformatics
Database systems and data warehousing, particularly efficiency issues

Naomi Nishimura

Algorithm design and analysis
Graph algorithms
Fixed-parameter tractability
Reconfiguration problems

Prabhakar Ragde

Design and analysis of algorithms
Graph-theoretic algorithms
Fixed-parameter tractable algorithms and parameterized complexity

Jeffrey O. Shallit

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

Douglas Stinson

Cryptography
Networks and distributed systems
Algorithms and computational complexity
Construction of combinatorial structures with applications in computer science and cryptography

John Watrous

Quantum complexity theory
Quantum information theory

Ph.D. Graduates

  • Peyman Afshani (Ph.D. 2008)

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

  • Mustaq Ahmed (Ph.D. 2009)

    Supervisor: Anna Lubiw
    Thesis title: Constrained Shortest Paths in Terrains and Graphs

  • Brona Brejova (Ph.D. 2005)

    Supervisors: Ming Li and Daniel Brown
    Thesis title: Evidence Combination in Hidden Markov Models for Gene Prediction

  • Christina Boucher (Ph.D. 2010)

    Supervisors: Daniel Brown and Prabhakar Ragde
    Thesis title: Evidence Combination in Hidden Markov Models for Gene Prediction

  • Eric Chen (Ph.D. 2009)

    Supervisor: Timothy Chan
    Thesis title: Solving Geometric Problems in Space-Conscious Models

  • Ehsan Chiniforooshan (Ph.D. 2007)

    Supervisor: Naomi Nishimura
    Thesis title: Intersperse Coloring

  • Erik Demaine (Ph.D. 2001)

    Supervisors: Anna Lubiw and Ian Munro
    Thesis title: Folding and Unfolding

  • Reza Dorrigiv (Ph.D. 2010)

    Supervisor: Alex Lopez-Ortiz
    Thesis title: Alternative Measures for the Analysis of Online Algorithms

  • Arash Farzan (Ph.D. 2009)

    Supervisor: Ian Munro
    Thesis title: Succinct Representation of Trees and Graphs

  • Robert Fraser (Ph.D. 2012)

    Supervisor: Alex Lopez-Ortiz
    Thesis title: Algorithms for Geometric Covering and Piercing Problems

  • Jianghai Fu (Ph.D. 1996)

    Supervisor: Naomi Nishimura
    Thesis title: Pattern Matching in Directed Graphs

  • Burkay Genc (Ph.D. 2008)

    Supervisor: Therese Biedl
    Thesis title: Reconstruction of Orthogonal Polyhedra

  • Alexander Golynski (Ph.D. 2007)

    Supervisors: Ian Munro and Prabhakar Ragde
    Thesis title: Upper and Lower Bounds for Text Indexing Data Structures

  • Gus Gutoski (Ph.D. 2009)

    Supervisors: John Watrous
    Thesis title: Quantum Strategies and Local Operations

  • Masud Hasan (Ph.D. 2005)

    Supervisors: Therese Biedl and Alex Lopez-Ortiz
    Thesis title: Reconstruction and Visualization of Polyhedra Using Projections

  • Meng He (Ph.D. 2008)

    Supervisor: Ian Munro
    Thesis title: Succinct Indexes

  • Jason Hinek (Ph.D. 2007)

    Supervisors: Douglas Stinson and Mark Giesbrecht
    Thesis title: On the Security of Some Variants of RSA

  • Alexander Hudek (Ph.D. 2010)

    Supervisor: Daniel Brown
    Thesis title: Improvements in the Accuracy of Pairwise Genomic Alignment

  • Tarique Islam (Ph.D. 2007)

    Supervisor: Jonathan Buss
    Thesis title: Characterizing Hardness in Parameterized Complexity

  • Krishnam Raju Jampani (Ph.D. 2011)

    Supervisor: Anna Lubiw
    Thesis title: Simultaneous Graph Representation Problems

  • Shahin Kamali (Ph.D. 2014)

    Supervisor: Alex Lopez-Ortiz
    Thesis title: Alternative Approaches for Analysis of Bin Packing and List Update Problems

  • Robin Kothari (Ph.D. 2014)

    Supervisor: John Watrous
    Thesis title: Efficient Algorithms in Quantum Query Complexity

  • Dalia Krieger (Ph.D. 2008)

    Supervisor: Jeffrey O. Shallit
    Thesis title: Critical Exponents and Stabilizers of Infinite Words

  • Mehdi Mirzazadeh (Ph.D. 2014)

    Supervisor: Alex Lopez-Ortiz
    Thesis title: Efficient Evaluation of Set Expressions

  • David Pal (Ph.D. 2009)

    Supervisor: Shai Ben-David
    Thesis title: Contribution to Unsupervised and Semi-Supervised Learning

  • Claude-Guy Quimper (Ph.D. 2006)

    Supervisor: Alex Lopez-Ortiz
    Thesis title: Efficient Propagators for Global Constraints

  • Bill Rosgen (Ph.D. 2009)

    Supervisor: John Watrous
    Thesis title: Computational Distinguishability of Quantum Channels

  • Ansis Rosmanis (Ph.D. 2014)

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

  • Alejandro Salinger (Ph.D. 2013)

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

  • Narges Simjour (Ph.D. 2013)

    Supervisor: Naomi Nishimura
    Thesis title: Parameterized Enumeration of Neighbor Strings and Kemeny Aggregations

  • Matthew Skala (Ph.D. 2008)

    Supervisor: Ian Munro
    Thesis title: Aspects of Metric Spaces in Computation

  • Michael J. Spriggs (Ph.D. 2006)

    Supervisors: Therese Biedl and Anna Lubiw
    Thesis title: Morphing Parallel Graph Drawings

  • Troy Vasiga (Ph.D. 2008)

    Supervisor: Jeffrey O. Shallit
    Thesis title: Error Detection in Number-Theoretic and Algebraic Algorithms

  • Tomas Vinar (Ph.D. 2005)

    Supervisors: Ming Li and Daniel Brown
    Thesis title: Enhancements to Hidden Markov Models for Gene Finding and Other Biological Applications

  • Ming-wei Wang (Ph.D. 2004)

    Supervisor: Jeffrey O. Shallit
    Thesis title: Periodicity and repetition in combinatorics on words

  • Jiang Wu (Ph.D. 2009)

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

  • Zhi Xu (Ph.D. 2009)

    Supervisor: Jeffrey O. Shallit
    Thesis title: The Frobenius Problems in a Free Monoid

  • Hamid Zarrabi-Zadeh (Ph.D. 2008)

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

M.Math. Graduates

  • Mustaq Ahmed (M.Math. 2004)

    Supervisor: Naomi Nishimura
    Thesis title: Ordered Interval Routing Schemes

  • Soroush Alamdari Hosseini (M.Math. 2012)

    Supervisor: Therese Biedl
    Thesis title: Planar Open Rectangle-of-Influence Drawings

  • Abdullah Al-Mahmood (M.Math. 2005)

    Supervisor: Timothy M. Chan
    Thesis title: Approximation Algorithms for Rectangle Piercing Problem

  • Terry Anderson (M.Math. 2011)

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

  • Thomas Ang (M.Math. 2010)

    Supervisor: Jeffrey O. Shallit
    Thesis title: Problems Related to Shortest Strings in Formal Languages

  • Kar Yee (Henry) Au (M.Math. 2005)

    Supervisor: Douglas Stinson
    Thesis title: Unconditionally Secure Authentication Codes and Digital Signatures

  • Shabnam Aziza (M.Math. 2004)

    Supervisor: Therese Biedl
    Thesis title: Hexagonal Grid Drawings

  • Stephen Bahun (M.Math. 2008)

    Supervisor: Anna Lubiw
    Thesis title: Algorithms for Optimizing Search Schedules in a Polygon

  • Adam Bains (M.Math. 2009)

    Supervisor: Therese Biedl
    Thesis title: Reconstructing hv-convex polyominoes with multiple colours

  • Hubert Chan (M.Math. 2003)

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

  • Eric Chen (M.Math. 2004)

    Supervisor: Timothy M. Chan
    Thesis title: Towards In-Place Algorithms in Computational Geometry

  • Albert Choi (M.Math. 2009)

    Supervisor: Ian Munro
    Thesis title: Distributed Policing with Full Utilization and Rate Guarantees

  • Michael Domaratzki (M.Math. 2001)

    Supervisor: Jeffrey O. Shallit
    Thesis title: Minimal covers of formal languages

  • Neeraj Dumir (M.Math. 2005)

    Supervisor: Ian Munro
    Thesis title: Improved Searching in the Presence of Permanent Faults

  • Keith Ellul (M.Math. 2002)

    Supervisor: Jeffrey O. Shallit
    Thesis title: Descriptional Complexity Measures of Regular Languages

  • Arash Farzan (M.Math. 2004)

    Supervisor: Ian Munro
    Thesis title: Cache-Oblivious Searching and Sorting In Multisets

  • Yashar Ganjali Gavgani (M.Math. 2001)

    Supervisor: Naomi Nishimura
    Thesis title: Multi-dimensional Interval Routing Schemes

  • Taylor Gordon (M.Math. 2010)

    Supervisor: Ian Munro
    Thesis title: Simultaneously Embedding Planar Graphs at Fixed Vertex Locations

  • MohammadTaghi Hajiaghayi (M.Math. 2001)

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

  • Ian Harrower (M.Math. 2005)

    Supervisor: Daniel Brown
    Thesis title: Haplotype inference using pure parsimony

  • Philip Henderson (M.Math. 2005)

    Supervisor: Therese Biedl
    Thesis title: Planar Graphs and Partial κ-Trees

  • Alexander Hudek (M.Math. 2004)

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

  • Bryan Krawetz (M.Math. 2004)

    Supervisor: Jeffrey O. Shallit
    Thesis title: Monoids and the state complexity of root(L)

  • Benjamin J. Lafreniere (M.Math. 2008)

    Supervisor: Anna Lubiw
    Thesis title: Packing Unit Disks

  • Alex Leong (M.Math. 2011)

    Supervisor: Jeffrey O. Shallit
    Thesis title: Variations on the Erdos Discrepancy Problem

  • Jiang Liu (M.Math. 2004)

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

  • Ying (Cathy) Liu (M.Math. 2010)

    Supervisor: Alex Lopez-Ortiz
    Thesis title: Geometric On-line Ray Searching Under Probability of Placement Scenarios

  • David Loker (M.Math. 2007)

    Supervisors: Kate Larson and Naomi Nishimura
    Thesis title: Representations and Parameterizations of Combinatorial Auctions

  • Lesley Macpherson (M.Math. 2002)

    Supervisor: Jeffrey O. Shallit
    Thesis title: Grey Level Visual Cryptography for General Access Structures

  • Andrew Martinez (M.Math. 2002)

    Supervisor: Jeffrey O. Shallit
    Thesis title: Topics in Formal Languages: String Enumeration, Unary NFA's, and State Complexity

  • Mehdi Mirzazadeh (M.Math. 2004)

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

  • Patrick Nicholson (M.Math. 2009)

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

  • Peter Olsar (M.Math. 2004)

    Supervisors: Naomi Nishimura and Prabhakar Ragde
    Thesis title: Updating the Vertex Separation of a Dynamically Changing Tree

  • Narad Rampersad (M.Math. 2004)

    Supervisor: Jeffrey O. Shallit
    Thesis title: Infinite Sequences and Pattern Avoidance

  • Mina Razaghpour (M.Math. 2008)

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

  • Elena Lesvia Ruiz Velazquez (M.Math. 2010)

    Supervisor: Therese Biedl
    Thesis title: Drawing planar graphs with prescribed face areas

  • Sayyed Bashir Sadjad (M.Math. 2004)

    Supervisor: Timothy M. Chan
    Thesis title: Geometric Optimization Problems over Sliding Windows and Similarity Search in Metric Spaces

  • Prashant Sasatte (M.Math. 2006)

    Supervisor: Jonathan Buss
    Thesis title: Cache Considerations in Algorithm Design

  • Narges Simjour (M.Math. 2006)

    Supervisor: Naomi Nishimura
    Thesis title: A New Optimality Measure for Distance Dominating Sets

  • Luke Tanur (M.Math. 2005)

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

  • Kamran Tirdad (M.Math. 2011)

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

  • Aleh Veraskouski (M.Math. 2007)

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

  • Dana Wilkinson (M.Math. 2002)

    Supervisor: Therese Biedl
    Thesis title: Bounded-Degree Independent Sets in Planar Graphs

  • Danny Sheng Zhang (M.Math. 2005)

    Supervisor: Douglas Stinson
    Thesis title: Algorithms for Detecting Cheaters in Threshold Schemes

  • Fengkai Zhang (M.Math. 2004)

    Supervisor: Daniel Brown
    Thesis title: Incoporating Spaced Seeds into PSI-BLAST Search

Events and Seminars

The Algorithms & Complexity group runs a weekly seminar, typically on Wednesday afternoons at 1:30pm. To receive announcements by email, subscribe to the student mailing list (for students at the University of Waterloo) or the general mailing list.

More Information

Prospective Faculty Members

The David R. Cheriton School of Computer Science at the University of Waterloo is currently hiring multiple tenure-track faculty members in all areas of computer science. More details on the openings and the application procedure can be found here.

Prospective Students

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.

Visitors

See here for directions and contact information.