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
Algorithms, especially for Graph Drawing, Computational Geometry, and Planar Graphs
Sublinear-time algorithms
Complexity of Boolean functions
Bioinformatics
Music Information Retrieval
Computational complexity
Models of feasible computation
Discrete and computational geometry
Design and analysis of algorithms
Quantum algorithms and complexity theory
Quantum information theory
Quantum communication complexity
Bioinformatics
Kolmogorov complexity
The Internet and the World Wide Web
Text-dominated databases/search engines
On-line Searching and Path Planning
Constraint Programming
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
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
Cryptography
Networks and distributed systems
Algorithms and computational complexity
Construction of combinatorial structures with applications in computer science and cryptography
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: John Watrous
Supervisor: Therese Biedl
Supervisor: Richard Cleve
Supervisor: Naomi Nishimura
Supervisor: Jeffrey Shallit
Supervisor: Anna Lubiw
Supervisor: Alex Lopez-Ortiz
Supervisor: John Watrous
Supervisor: Timothy Chan
Supervisor: Anna Lubiw
M.Math. Candidates
Supervisor: Alex Lopez-Ortiz
Supervisors: Therese Biedl
Supervisor: Jeffrey Shallit
Supervisor: Ian Munro
Supervisor: Ian Munro
Supervisor: Anna Lubiw
Supervisors: Therese Biedl and Sebastian Fischmeister
Supervisors: Therese Biedl and Timothy Chan
Supervisor: Timothy Chan
Supervisor: Timothy Chan
Supervisor: Ian Munro
Supervisor: Naomi Nishimura
Supervisor: John Watrous
Supervisor: Ian Munro
Ph.D. Graduates
Supervisor: Timothy Chan
Thesis title: On Geometric Range Searching, Approximate Counting and Depth Problems
Supervisor: Anna Lubiw
Thesis title: Constrained Shortest Paths in Terrains and Graphs
Supervisors: Ming Li and Daniel Brown
Thesis title: Evidence Combination in Hidden Markov Models for Gene Prediction
Supervisors: Daniel Brown and Prabhakar Ragde
Thesis title: Evidence Combination in Hidden Markov Models for Gene Prediction
Supervisor: Timothy Chan
Thesis title: Solving Geometric Problems in Space-Conscious Models
Supervisor: Naomi Nishimura
Thesis title: Intersperse Coloring
Supervisors: Anna Lubiw and Ian Munro
Thesis title: Folding and Unfolding
Supervisor: Alex Lopez-Ortiz
Thesis title: Alternative Measures for the Analysis of Online Algorithms
Supervisor: Ian Munro
Thesis title: Succinct Representation of Trees and Graphs
Supervisor: Alex Lopez-Ortiz
Thesis title: Algorithms for Geometric Covering and Piercing Problems
Supervisor: Naomi Nishimura
Thesis title: Pattern Matching in Directed Graphs
Supervisor: Therese Biedl
Thesis title: Reconstruction of Orthogonal Polyhedra
Supervisors: Ian Munro and Prabhakar Ragde
Thesis title: Upper and Lower Bounds for Text Indexing Data Structures
Supervisors: John Watrous
Thesis title: Quantum Strategies and Local Operations
Supervisors: Therese Biedl and Alex Lopez-Ortiz
Thesis title: Reconstruction and Visualization of Polyhedra Using Projections
Supervisor: Ian Munro
Thesis title: Succinct Indexes
Supervisors: Douglas Stinson and Mark Giesbrecht
Thesis title: On the Security of Some Variants of RSA
Supervisor: Daniel Brown
Thesis title: Improvements in the Accuracy of Pairwise Genomic Alignment
Supervisor: Jonathan Buss
Thesis title: Characterizing Hardness in Parameterized Complexity
Supervisor: Anna Lubiw
Thesis title: Simultaneous Graph Representation Problems
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: Jeffrey O. Shallit
Thesis title: Critical Exponents and Stabilizers of Infinite Words
Supervisor: Alex Lopez-Ortiz
Thesis title: Efficient Evaluation of Set Expressions
Supervisor: Shai Ben-David
Thesis title: Contribution to Unsupervised and Semi-Supervised Learning
Supervisor: Alex Lopez-Ortiz
Thesis title: Efficient Propagators for Global Constraints
Supervisor: John Watrous
Thesis title: Computational Distinguishability of Quantum Channels
Supervisor: John Watrous
Thesis title: Lower Bounds on Quantum Query and Learning Graph Complexities
Supervisor: Alex Lopez-Ortiz
Thesis title: Models for Parallel Computation in Multi-Core, Heterogeneous, and Ultra Wide-Word Architectures
Supervisor: Naomi Nishimura
Thesis title: Parameterized Enumeration of Neighbor Strings and Kemeny Aggregations
Supervisor: Ian Munro
Thesis title: Aspects of Metric Spaces in Computation
Supervisors: Therese Biedl and Anna Lubiw
Thesis title: Morphing Parallel Graph Drawings
Supervisor: Jeffrey O. Shallit
Thesis title: Error Detection in Number-Theoretic and Algebraic Algorithms
Supervisors: Ming Li and Daniel Brown
Thesis title: Enhancements to Hidden Markov Models for Gene Finding and Other Biological Applications
Supervisor: Jeffrey O. Shallit
Thesis title: Periodicity and repetition in combinatorics on words
Supervisor: Douglas Stinson
Thesis title: Cryptographic Protocols, Sensor Network Key Management, and RFID Authentication
Supervisor: Jeffrey O. Shallit
Thesis title: The Frobenius Problems in a Free Monoid
Supervisor: Timothy Chan
Thesis title: Geometric Approximation Algorithms in the Online and Data Stream Models
M.Math. Graduates
Supervisor: Naomi Nishimura
Thesis title: Ordered Interval Routing Schemes
Supervisor: Therese Biedl
Thesis title: Planar Open Rectangle-of-Influence Drawings
Supervisor: Timothy M. Chan
Thesis title: Approximation Algorithms for Rectangle Piercing Problem
Supervisor: Therese Biedl
Thesis title: The Vulcan game of Kal-toh: Finding or making triconnected planar subgraphs
Supervisor: Jeffrey O. Shallit
Thesis title: Problems Related to Shortest Strings in Formal Languages
Supervisor: Douglas Stinson
Thesis title: Unconditionally Secure Authentication Codes and Digital Signatures
Supervisor: Therese Biedl
Thesis title: Hexagonal Grid Drawings
Supervisor: Anna Lubiw
Thesis title: Algorithms for Optimizing Search Schedules in a Polygon
Supervisor: Therese Biedl
Thesis title: Reconstructing hv-convex polyominoes with multiple colours
Supervisor: Naomi Nishimura
Thesis title: A Parameterized Algorithm for Upward Planarity Testing of Biconnected Graphs
Supervisor: Timothy M. Chan
Thesis title: Towards In-Place Algorithms in Computational Geometry
Supervisor: Ian Munro
Thesis title: Distributed Policing with Full Utilization and Rate Guarantees
Supervisor: Jeffrey O. Shallit
Thesis title: Minimal covers of formal languages
Supervisor: Ian Munro
Thesis title: Improved Searching in the Presence of Permanent Faults
Supervisor: Jeffrey O. Shallit
Thesis title: Descriptional Complexity Measures of Regular Languages
Supervisor: Ian Munro
Thesis title: Cache-Oblivious Searching and Sorting In Multisets
Supervisor: Naomi Nishimura
Thesis title: Multi-dimensional Interval Routing Schemes
Supervisor: Ian Munro
Thesis title: Simultaneously Embedding Planar Graphs at Fixed Vertex Locations
Supervisor: Naomi Nishimura
Thesis title: Algorithms for Graphs of (Locally) Bounded Treewidth
Supervisor: Daniel Brown
Thesis title: Haplotype inference using pure parsimony
Supervisor: Therese Biedl
Thesis title: Planar Graphs and Partial κ-Trees
Supervisor: Daniel Brown
Thesis title: New anchoring techniques for global multiple alignment of genomic sequences
Supervisor: Jeffrey O. Shallit
Thesis title: Monoids and the state complexity of root(L)
Supervisor: Anna Lubiw
Thesis title: Packing Unit Disks
Supervisor: Jeffrey O. Shallit
Thesis title: Variations on the Erdos Discrepancy Problem
Supervisor: Daniel Brown
Thesis title: A Combinatorial Approach for Motif Discovery in Unaligned DNA Sequences
Supervisor: Alex Lopez-Ortiz
Thesis title: Geometric On-line Ray Searching Under Probability of Placement Scenarios
Supervisors: Kate Larson and Naomi Nishimura
Thesis title: Representations and Parameterizations of Combinatorial Auctions
Supervisor: Jeffrey O. Shallit
Thesis title: Grey Level Visual Cryptography for General Access Structures
Supervisor: Jeffrey O. Shallit
Thesis title: Topics in Formal Languages: String Enumeration, Unary NFA's, and State Complexity
Supervisor: Naomi Nishimura
Thesis title: Adaptive Comparison-Based Algorithms for Evaluating Set Queries
Supervisor: Ian Munro
Thesis title: The application of the in-tree knapsack problem to routing prefix caches
Supervisors: Naomi Nishimura and Prabhakar Ragde
Thesis title: Updating the Vertex Separation of a Dynamically Changing Tree
Supervisor: Jeffrey O. Shallit
Thesis title: Infinite Sequences and Pattern Avoidance
Supervisor: Anna Lubiw
Thesis title: The Steiner ratio for the obstacle-avoiding Steiner tree problem
Supervisor: Therese Biedl
Thesis title: Drawing planar graphs with prescribed face areas
Supervisor: Timothy M. Chan
Thesis title: Geometric Optimization Problems over Sliding Windows and Similarity Search in Metric Spaces
Supervisor: Jonathan Buss
Thesis title: Cache Considerations in Algorithm Design
Supervisor: Naomi Nishimura
Thesis title: A New Optimality Measure for Distance Dominating Sets
Supervisor: Anna Lubiw
Thesis title: A Geometric Approach to Pattern Matching in Polyphonic Music
Supervisor: Ian Munro
Thesis title: Exploiting the Computational Power of Ternary Content Addressable Memory
Supervisor: Jeremy Barbay
Thesis title: Adaptive Algorithms for Weighted Queries on Weighted Binary Relations and Labeled Trees
Supervisor: Therese Biedl
Thesis title: Bounded-Degree Independent Sets in Planar Graphs
Supervisor: Douglas Stinson
Thesis title: Algorithms for Detecting Cheaters in Threshold Schemes
Supervisor: Daniel Brown
Thesis title: Incoporating Spaced Seeds into PSI-BLAST Search
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.
Fall 2014 Graduate Courses
Bin Ma
Richard Cleve
Ian Munro
Anna Lubiw
Eric Blais
John Watrous
The David R. Cheriton School of Computer Science at the University of Waterloo is currently hiring
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.
See here for directions and contact information.