Sotabase

Career

· Researcher, Algorithms and Complexity Group, University of Waterloo2024–
· Graduate Student (Master's), University of Waterloo, Algorithms and Complexity Group2023–

Publications (26)

Nondeterminism Within P
SIAM journal on computing (Print) · 1993
310
cited
Pattern Matching for Permutations
Workshop on Algorithms and Data Structures · 1993
237
cited
The Computational Complexity of Some Problems of Linear Algebra
Journal of computer and system sciences (Print) · 1996
173
cited
A sublinear space, polynomial time algorithm for directed s-t connectivity
[1992] Proceedings of the Seventh Annual Structure in Complexity Theory Conference · 1992
82
cited
Parallel Algorithms with Processor Failures and Delays
J. Algorithms · 1996
66
cited
On the pagenumber of planar graphs
Symposium on the Theory of Computing · 1984
59
cited
Relativized Alternation and Space-Bounded Computation
Journal of computer and system sciences (Print) · 1988
39
cited
Vertex Types in Book-Embeddings
SIAM Journal on Discrete Mathematics · 1987
16
cited
Lower Bounds on Universal Traversal Sequences Based on Chains of Length Five
Information and Computation · 1995
15
cited
Relativized Alternation
Symposium on Computation Theory · 1986
12
cited
Simplifying the Weft Hierarchy
IWPEC · 2004
11
cited
How hard are n2-hard problems?
SIGA · 1994
10
cited
Algorithms in the W-Hierarchy
Theory of Computing Systems · 2007
9
cited
How Hard Are n 2-Hard Problems ?
1994
8
cited
Number of variables is equivalent to space
Journal of Symbolic Logic (JSL) · 2001
8
cited
Sharply Bounded Alternation and Quasilinear Time
Theory of Computing Systems · 1998
6
cited
Sharply Bounded Alternation within P
International Conference on Discrete Mathematics and Theoretical Computer Science · 1996
5
cited
Nondterminism Within P
Symposium on Theoretical Aspects of Computer Science · 1991
4
cited
Imbalance, Cutwidth, and the Structure of Optimal Orderings
International Computing and Combinatorics Conference · 2019
3
cited
Palindrome Re ognition Using a Multidimensional Tape
2021
3
cited
Sotabase
Jonathan Buss | Researcher Profile | Sotabase | Sotabase