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

Lap Chi Lau

Algorithmic graph theory
Approximation algorithms
Spectral graph theory

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. Candidates

Alessandro Cosentino

Supervisor: John Watrous

  • Martin Derka

    Supervisor: Therese Biedl

  • Li Liu

    Supervisor: Richard Cleve

  • Amer Mouawad

    Supervisor: Naomi Nishimura

  • Jazmin Romero

    Supervisor: Alex Lopez-Ortiz

  • Vincent Russo

    Supervisor: John Watrous

  • Dimitrios Skrepetos

    Supervisor: Timothy Chan

  • Hamide Vosoughpour

    Supervisor: Anna Lubiw

  • M.Math. Candidates

  • Alexandre Daigle

    Supervisor: Alex Lopez-Ortiz

  • Philippe Demontigny

    Supervisor: Therese Biedl

  • Chen Fei Du

    Supervisor: Jeffrey Shallit

  • Hicham El-Zein

    Supervisor: Ian Munro

  • Zachary Frenette

    Supervisor: Ian Munro

  • Neeraj Kumar

    Supervisors: Therese Biedl and Sebastian Fischmeister

  • Stephanie Lee

    Supervisors: Therese Biedl and Timothy Chan

  • Jason Lin

    Supervisor: Timothy Chan

  • Simon Pratt

    Supervisor: Timothy Chan

  • Matthew Robertson

    Supervisor: Ian Munro

  • Vijay Subramanya

    Supervisor: Naomi Nishimura

  • Youcef Tebbal

    Supervisor: Naomi Nishimura

  • Alex Valtchev

    Supervisor: John Watrous

  • Siwei Yang

    Supervisor: Ian Munro

  • Ph.D. Graduates

    Vinayak Pathak (Ph.D. 2015)

    Supervisor: Anna Lubiw
    Thesis title: Reconfiguring Triangulations

    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

    Ansis Rosmanis (Ph.D. 2014)

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

    Mehdi Mirzazadeh (Ph.D. 2014)

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

    Narges Simjour (Ph.D. 2013)

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

    Alejandro Salinger (Ph.D. 2013)

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

    Robert Fraser (Ph.D. 2013)

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

    Krishnam Raju Jampani (Ph.D. 2011)

    Supervisor: Anna Lubiw
    Thesis title: Simultaneous Graph Representation Problems

    Christina Boucher (Ph.D. 2010)

    Supervisors: Daniel Brown and Prabhakar Ragde
    Thesis title: Combinatorial and Probabilistic Approaches to Motif Recognition

    Alexander Hudek (Ph.D. 2010)

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

    Reza Dorrigiv (Ph.D. 2010)

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

    Gus Gutoski (Ph.D. 2010)

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

    Arash Farzan (Ph.D. 2009)

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

    Mustaq Ahmed (Ph.D. 2009)

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

    Bill Rosgen (Ph.D. 2009)

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

    Zhi Xu (Ph.D. 2009)

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

    Jiang Wu (Ph.D. 2009)

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

    David Pal (Ph.D. 2009)

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

    Eric Chen (Ph.D. 2009)

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

    Hamid Zarrabi-Zadeh (Ph.D. 2008)

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

    Peyman Afshani (Ph.D. 2008)

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

    Troy Vasiga (Ph.D. 2008)

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

    Matthew Skala (Ph.D. 2008)

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

    Dalia Krieger (Ph.D. 2008)

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

    Burkay Genc (Ph.D. 2008)

    Supervisor: Therese Biedl
    Thesis title: Reconstruction of Orthogonal Polyhedra

    Meng He (Ph.D. 2008)

    Supervisor: Ian Munro
    Thesis title: Succinct Indexes

    Alexander Golynski (Ph.D. 2008)

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

    Ehsan Chiniforooshan (Ph.D. 2007)

    Supervisor: Naomi Nishimura
    Thesis title: Intersperse Coloring

    Michael J. Spriggs (Ph.D. 2007)

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

    Tarique Islam (Ph.D. 2007)

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

    Jason Hinek (Ph.D. 2007)

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

    Claude-Guy Quimper (Ph.D. 2006)

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

    Brona Brejova (Ph.D. 2005)

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

    Masud Hasan (Ph.D. 2005)

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

    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 Shallit
    Thesis title: Periodicity and repetition in combinatorics on words

    Erik Demaine (Ph.D. 2001)

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

  • Jianghai Fu (Ph.D. 1996)

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

  • M.Math. Graduates

    Stephen Kiazyk (M.Math. 2014)

    Supervisor: Anna Lubiw
    Thesis title: The Star Unfolding from a Geodesic Curve

    Soroush Hosseini Alamdari (M.Math. 2012)

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

    Alex Leong (M.Math. 2012)

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

    Kamran Tirdad (M.Math. 2011)

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

    Vinayak Pathak (M.Math. 2011)

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

    Terry Anderson (M.Math. 2011)

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

    Ying Liu (M.Math. 2010)

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

    Elena Lesvia Ruiz Velazquez (M.Math. 2010)

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

    Taylor Gordon (M.Math. 2010)

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

    Thomas Ang (M.Math. 2010)

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

    Albert Choi (M.Math. 2009)

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

    Adam Bains (M.Math. 2009)

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

    Patrick Nicholson (M.Math. 2009)

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

    Mina Razaghpour (M.Math. 2008)

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

    Stephen Bahun (M.Math. 2008)

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

    Benjamin J. Lafreniere (M.Math. 2008)

    Supervisor: Anna Lubiw
    Thesis title: Packing Unit Disks

    David Loker (M.Math. 2007)

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

    Aleh Veraskouski (M.Math. 2007)

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

  • 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

    Abdullah Al-Mahmood (M.Math. 2005)

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

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

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

  • Neeraj Dumir (M.Math. 2005)

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

  • 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 k-Trees

  • Luke Tanur (M.Math. 2005)

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

  • Danny Sheng Zhang (M.Math. 2005)

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

  • Mustaq Ahmed (M.Math. 2004)

    Supervisor: Naomi Nishimura
    Thesis title: Ordered Interval Routing Schemes

  • Shabnam Aziza (M.Math. 2004)

    Supervisor: Therese Biedl
    Thesis title: Hexagonal Grid Drawings

  • 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 Shallit
    Thesis title: Monoids and the state complexity of root(L)

  • Eric Chen (M.Math. 2004)

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

  • Arash Farzan (M.Math. 2004)

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

  • Jiang Liu (M.Math. 2004)

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

  • 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 Shallit
    Thesis title: Infinite Sequences and Pattern Avoidance

    Mehdi Mirzazadeh (M.Math. 2004)

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

  • Sayyed Bashir Sadjad (M.Math. 2004)

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

  • Fengkai Zhang (M.Math. 2004)

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

  • Hubert Chan (M.Math. 2003)

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

  • Keith Ellul (M.Math. 2002)

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

  • Lesley Macpherson (M.Math. 2002)

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

  • Andrew Martinez (M.Math. 2002)

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

  • Dana Wilkinson (M.Math. 2002)

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

  • Michael Domaratzki (M.Math. 2001)

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

  • Yashar Ganjali (M.Math. 2001)

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

  • MohammadTaghi Hajiaghayi (M.Math. 2001)

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

  • Events and Seminars

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

    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.

    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.