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

Lecturing

In Spring 2014, I will teach the graduate course CS 764, Computational Complexity. Interested and/or curious students—both graduate and undergraduate—should see the course web page or contact me via email for more information.

I have taught the courses listed below at various times.

CS 240: Data Structures and Data Management (formerly Data Structures and Algorithms)
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

Research

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.

Jonathan F. Buss
School of Computer Science
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1

jfbuss@uwaterloo.ca