|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.|
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.
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.
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
Canada N2L 3G1