Jonathan F. Buss

According to our database, Jonathan F. Buss authored at least 24 papers between 1984 and 2019.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2019

Imbalance, Cutwidth, and the Structure of Optimal Orderings.

Jan Gorzny, Jonathan F. Buss

Proceedings of the Computing and Combinatorics - 25th International Conference, 2019

2008

The complexity of fixed-parameter problems: guest column.

Jonathan F. Buss, Tarique Mesbaul Islam

SIGACT News, 2008

2007

Algorithms in the W-Hierarchy.

Jonathan F. Buss, Tarique Islam

Theory Comput. Syst., 2007

2006

Simplifying the weft hierarchy.

Jonathan F. Buss, Tarique Islam

Theor. Comput. Sci., 2006

2003

Palindrome recognition using a multidimensional tape.

Therese Biedl, Jonathan F. Buss, Erik D. Demaine, Martin L. Demaine, Mohammad Taghi Hajiaghayi, Tomás Vinar

Theor. Comput. Sci., 2003

2001

Number of Variables Is Equivalent to Space.

Neil Immerman, Jonathan F. Buss, David A. Mix Barrington

J. Symb. Log., 2001

1999

The Computational Complexity of Some Problems of Linear Algebra.

Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit

J. Comput. Syst. Sci., 1999

1998

A Sublinear Space, Polynomial Time Algorithm for Directed <i>s</i>-<i>t</i> Connectivity.

Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, Baruch Schieber

SIAM J. Comput., 1998

Sharply Bounded Alternation and Quasilinear Time.

Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith

Theory Comput. Syst., 1998

Pattern Matching for Permutations.

Prosenjit Bose, Jonathan F. Buss, Anna Lubiw

Inf. Process. Lett., 1998

1997

The Computational Complexity of Some Problems of Linear Algebra (Extended Abstract).

Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

1996

Parallel Algorithms with Processor Failures and Delays.

Jonathan F. Buss, Paris C. Kanellakis, Prabhakar Ragde, Alexander A. Shvartsman

J. Algorithms, 1996

Sharply Bounded Alternation within P

Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith

Electron. Colloquium Comput. Complex., 1996

1995

Lower Bounds on Universal Traversal Sequences Based on Chains of Length Five

Jonathan F. Buss, Martin Tompa

Inf. Comput., August, 1995

1994

How hard are n2-hard problems?

Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith

SIGACT News, 1994

1993

Nondeterminism Within P.

Jonathan F. Buss, Judy Goldsmith

SIAM J. Comput., 1993

1992

A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity

Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, Baruch Schieber

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991

Nondterminism Within P.

Jonathan F. Buss, Judy Goldsmith

Proceedings of the STACS 91, 1991

1990

Processor Networks and Alternating Machines.

Jonathan F. Buss

Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990

1989

Vertex Types in Book-Embeddings.

Jonathan F. Buss, Arnold L. Rosenberg, Judson D. Knott

SIAM J. Discret. Math., 1989

1988

Relativized Alternation and Space-Bounded Computation.

Jonathan F. Buss

J. Comput. Syst. Sci., 1988

1987

A theory of oracle machines.

Jonathan F. Buss

Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

1986

Relativized Alternation.

Jonathan F. Buss

Proceedings of the Structure in Complexity Theory, 1986

1984

On the Pagenumber of Planar Graphs

Jonathan F. Buss, Peter W. Shor

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984