Stephen R. Mahaney

According to our database, Stephen R. Mahaney authored at least 25 papers between 1978 and 1998.

Collaborative distances:

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

1998

L-Printable Sets.

Lance Fortnow, Judy Goldsmith, Matthew A. Levy, Stephen R. Mahaney

SIAM J. Comput., 1998

1997

Strategic directions in research in theory of computing.

Anne Condon, Faith E. Fich, Greg N. Frederickson, Andrew V. Goldberg, David S. Johnson, Michael C. Loui, Steven Mahaney, Prabhakar Raghavan, John E. Savage, Alan L. Selman, David B. Shmoys

SIGACT News, 1997

A Quasi-Polynomial-Time Algorithm for Sampling Words from a Context-Free Language.

Vivek Gore, Mark Jerrum, Sampath Kannan, Z. Sweedyk, Stephen R. Mahaney

Inf. Comput., 1997

1996

Foreword.

Fred S. Roberts, Bernard Chazelle, Stephen R. Mahaney

Proceedings of the Spin Verification System, 1996

Active transport in biological computing.

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer, Janos Simon

Proceedings of the DNA Based Computers, 1996

L-Printable Sets.

Lance Fortnow, Judy Goldsmith, Stephen R. Mahaney

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995

The Isomorphism Conjecture Fails Relative to a Random Oracle.

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

J. ACM, 1995

Counting and Random Generation of Strings in Regular Languages.

Sampath Kannan, Z. Sweedyk, Stephen R. Mahaney

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

1992

Average Dependence and Random Oracles.

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

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

1989

Relativizing Relativized Computations.

Neil Immerman, Stephen R. Mahaney

Theor. Comput. Sci., 1989

The Isomorphism Conjecture Fails Relative to a Random Oracle (Extended Abstract)

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

The Isomorphism Conjecture Fails Relative to a Random Oracle (abstract).

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988

Collapsing Degrees.

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

J. Comput. Syst. Sci., 1988

On the Power of 1-way Functions (Abstract).

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Proceedings of the Advances in Cryptology, 1988

1987

Progress on collapsing degrees.

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

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

1986

Polygon Containment under Translation.

Brenda S. Baker, Steven Fortune, Stephen R. Mahaney

J. Algorithms, 1986

Collapsing Degrees (Extended Abstract)

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985

Reductions Among Polynomial Isomorphism Types.

Stephen R. Mahaney, Paul Young

Theor. Comput. Sci., 1985

Inexact Agreement: Accuracy, Precision, and Graceful Degradation.

Stephen R. Mahaney, Fred B. Schneider

Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, 1985

1982

Sparse Complete Sets of NP: Solution of a Conjecture of Berman and Hartmanis.

Stephen R. Mahaney

J. Comput. Syst. Sci., 1982

1981

Sparse NP-Complete Sets.

Stephen R. Mahaney

PhD thesis, 1981

Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata.

Juris Hartmanis, Stephen R. Mahaney

SIAM J. Comput., 1981

On the Number of P-Isomorphism Classes of NP-Complete Sets

Stephen R. Mahaney

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980

An Eassay about Research on Sparse NP Complete Sets.

Juris Hartmanis, Stephen R. Mahaney

Proceedings of the Mathematical Foundations of Computer Science 1980 (MFCS'80), 1980

1978

One-Way Log-Tape Reductions

Juris Hartmanis, Neil Immerman, Stephen R. Mahaney

Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978