Processor Networks and Alternating Machines (2007)
Internally monotone networks of processors are defined and discussed. Internally monotone networks are shown to be equivalent to alternating machines, in which the memory-access structure of the...
Therese Biedl, Jonathan F. Buss, Erik D. Demaine, Martin L. Demaine, Mohammadtaghi Hajiaghayi
y, Tomas Vinar
Therese Biedl, Jonathan F. Buss, Erik D. Demaine, Martin L. Demaine, Mohammadtaghi Hajiaghayi
y, Tomas Vinar
PATTERN MATCHING FOR PERMUTATIONS # Prosenjit Bose 1 (2007)
Given a permutation T of 1 to n, and a permutation P of 1 to k, for k n, we wish to find a k-element subsequence of T whose elements are ordered according to the permutation P. For example, if P is...
The computational complexity of some problems of linear algebra (1999)
Jonathan F. Buss, Jonathan F. Buss, Gudmund S. Frandsen, Gudmund S. Frandsen, Jeffrey O. Shallit, Jeffrey O. Shallit
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
Number of Variables Is Equivalent To Space (1999)
Neil Immerman, Jonathan F. Buss
We prove that the set of properties describable by a uniform sequence of firstorder sentences using at most k + 1 distinct variables is exactly equal to the set of properties checkable by a Turing...
The computational complexity of some problems of linear algebra (1999)
Jonathan F. Buss, Gudmund S. Frandsen, Jeffrey O. Shallit, Jeffrey O. Shallit
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
Parallel Algorithms with Processor Failures and Delays. (1998)
Buss, Jonathan F., Kanellakis, Paris C., Radge, Prabhakar L., Shvartsman, Alex A.
We study efficient deterministic parallel algorithms on two models: restartable fail-stop CRCW PRAMs and strongly asynchronous PRAMs. In the first model, synchronous processors are subject to...
Sharply bounded alternation and quasilinear time (1998)
Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith
We de ne the sharply bounded hierarchy, SBH (QL), a hierarchy of classes within P, using quasilinear-time computation and quanti cation over strings of length log n. It generalizes the limited...
Sharply Bounded Alternation and Quasilinear Time (1997)
Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith
We define the sharply bounded hierarchy, SBH (QL), a hierarchy of classes within P , using quasilinear-time computation and quantification over strings of length log n. It generalizes the limited...
The Computational Complexity of Some Problems of Linear Algebra (1997)
Jonathan F. Buss, Gudmund S. Frandsen, Jeffrey O. Shallit
We consider the computational complexity of some problems dealing with matrix rank. Let E; S be subsets of a commutative ring R. Let x 1 ; x 2 ; : : : ; x t be variables. Given a matrix M = M(x 1 ; x...
The Computational Complexity of Some Problems of Linear Algebra (1997)
Jonathan F. Buss, Gudmund S. Frandsen, Jeffrey O. Shallit
We consider the computational complexity of some problems dealing with matrix rank. Let E; S be subsets of a commutative ring R. Let x 1 ; x 2 ; : : : ; x t be variables. Given a matrix M = M(x 1 ; x...
Sharply Bounded Alternation within P (1996)
Within P, Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith
We define the sharply bounded hierarchy, SBH (QL), a hierarchy of classes within P , using quasilinear-time computation and quantification over values of length log n. It generalizes the limited...
Lower Bounds on Universal Traversal Sequences Based on Chains of Length Five (1995)
Jonathan F. Buss, Martin Tompa
Universal traversal sequences for cycles require length\Omega\Gamma n 1:43 ), improving the previous bound of \Omega\Gamma n 1:33 ). For d 3, universal traversal sequences for d-regular graphs...
Parallel Algorithms with Processor Failures and Delays (1995)
Jonathan F. Buss, Paris C. Kanellakis, Prabhakar L. Ragde, Alex A. Shvartsman
We study efficient deterministic parallel algorithms on two models: restartable fail-stop CRCW PRAMs and asynchronous PRAMs. In the first model, synchronous processors are subject to arbitrary stop...
Sharply Bounded Alternation within P (1995)
Within P, Jonathan F. Buss, Judy Goldsmith
We define the sharply bounded hierarchy, SBH (QL), a hierarchy of classes within P , using quasilinear-time computation and quantification over values of length log n.
How hard are n 2 -hard problems (1994)
Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith
Many of the \n 2-hard " problems described by Gajentaan and Overmars can be solved using limited nondeterminism or other sharply-bounded quanti ers. Thus we suggest that these problems are...
Pattern Matching For Permutations (1993)
Prosenjit Bose, Jonathan F. Buss, Anna Lubiw
Given a permutation T of 1 to n, and a permutation P of 1 to k, for k n, we wish to find a k-element subsequence of T whose elements are ordered according to the permutation P . For example, if P is...
A Sublinear Space, Polynomial Time Algorithm for Directed (1992)
Connectivity Greg Barnes, Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, Baruch Schieber
Directed s-t connectivity is the problem of detecting whether there is a path from vertex s to vertex t in a directed graph. We present the first known deterministic sublinear space, polynomial time...
A Sublinear Space, Polynomial Time Algorithm for Directed (1992)
Connectivity Greg, Baruch Schieber, Greg Barnes, Greg Barnes, Jonathan F. Buss, Jonathan F. Buss, ...
Directed s-t connectivity is the problem of detecting whether there is a path from vertex s to vertex t in a directed graph. We present the first known deterministic sublinear space, polynomial time...