Jonathan Buss

(picture of Prof. Buss) 

Good morning! from the Cheriton School of Computer Science in the Faculty of Mathematics of the University of Waterloo. I work in the Algorithms and Complexity Group.

Phone: 1-519-888-4567 x34428
Office: DC 3353
email: jfbuss á


In Spring 2017, I will teach CS 245, Logic and Computation, and also co-teach CS 466/666, Algorithm Design & Analysis.

I have taught the following courses at various times.

CS 240: Data Structures and Data Management
CS 245: Logic and Computation
CS 251: Computer Organization and Design (formerly Digital Design and Architecture)
CS 341: Algorithms
CS 360: Introduction to Theory of Computation
CS 365: Models of Computation
CS 462/662: Formal Languages and Parsing
CS 464/664: Computational Complexity Theory (no longer offered; see CS 764)
CS 466/666: Algorithm Design and Analysis
CS 764: Computational Complexity
CS 860: Advanced Topics in Algorithms and Complexity


My research work concerns computational complexity and models of feasible computation. In particular, I study subsets of "polynomial time" problems, which better capture the feasibility of computations. Lately I have extended the scope to include the "W-hierarchy" of (possibly) "fixed-parameter intractable" problems.

Some selected papers

J.F. Buss, T.M. Islam, "The complexity of fixed-parameter problems: guest column," SIGACT News 39(2008) 33–46.

J.F. Buss, T. Islam, "Algorithms in the W-Hierarchy," Theory of Computer Systems 41 (2007) 445–457.

J.F. Buss and T. Islam, ``Simplifying the Weft Hierarchy,'' Theoretical Computer Science 351 (2006) 303–313. (Original version in International Workshop on Parameterized and Exact Computation (IWPEC 2004), Springer, 2004.)

T. Biedl, et al., ``Palindrome Recognition Using a Multidimensional Tape,'' Theoretical Computer Science, 2003.

N. Immerman, J.F. Buss, and D.A. Mix Barrington, ``Number of Variables Is Equivalent To Space,'' J. Symbolic Logic 66 (2001) 1217–1230.

J.F. Buss, G.S. Frandsen, and J.O. Shallit, ``The Computational Complexity of Some Problems in Linear Algebra,'' J. Computer and System Sciences 58 (1999) 572–596.

J.F. Buss and R.B. Simpson, ``Planar Mesh Refinement Cannot Be Both Local and Regular,'' Numerische Mathematik 79,1 (1998) 1–10.

S.A. Bloch, J.F. Buss and J. Goldsmith, ``Sharply-Bounded Alternation and Quasilinear Time,'' Theory of Computing Systems 31 (1998) 187-214.

P. Bose, J.F. Buss and A. Lubiw, ``Pattern Matching for Permutations,'' Information Processing Letters 65,5 (1998) 277-283.

A Sublinear-Space, Polynomial-Time Algorithm for Directed s-t Connectivity, 1992, with co-authors Greg Barnes, Larry Ruzzo, and Baruch Schieber.

Sharply Bounded Alternation within P, 1995, with co-authors Stephen Bloch and Judy Goldsmith. Archived by the Electronic Colloquium on Computational Complexity.

Parallel Algorithms with Processor Failures and Delays, 1991, with co-authors Paris Kanellakis, Prabhakar Ragde, and Alex Shvartsman.

Lower Bounds on Universal Traversal Sequences Based on Chains of Length Five , 1993, with co-author Martin Tompa.

Processor Networks and Alternation Machines, Symposium on Parallel Algorithms and Architectures (SPAA), 1990.