Juris Hartmanis

According to our database1, Juris Hartmanis
  • authored at least 131 papers between 1959 and 2012.
  • has a "Dijkstra number"2 of two.

Awards

Turing Prize recipient

Turing Prize 1993, "In recognition of their seminal paper which established the foundations for the field of computational complexity theory." awarded to Juris Hartmanis and Richard E. Stearns.

ACM Fellow

ACM Fellow 1994, "In recognition of their seminal paper which established the foundations for the field of computational complexity theory.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2012
Turing Machine-Inspired Computer Science Results.
Proceedings of the How the World Computes, 2012

The Turing Computational Model.
Proceedings of the ACM Turing Centenary Celebration, 2012

2003
Separation of complexity classes.
J. ACM, 2003

2002
The Separation Problems and Descriptional Complexity.
Proceedings of the Fourth International Workshop on Descriptional Complexity of Formal Systems - DCFS 2002, London, Canada, August 21, 2002

2001
Computational Complexity and Mathematical Proofs.
Proceedings of the Informatics - 10 Years Back. 10 Years Ahead., 2001

2000
Undecidability and Incompleteness Results in Automata Theory.
Proceedings of the A Half-Century of Automata Theory: Celebration and Inspiration, 2000

1999
Observations about the Nature and State of Computer Science (Keynote Address).
Proceedings of the Automata, 1999

1998
Innovation and Obstacles: The Future of Computing.
IEEE Computer, 1998

1995
On the Weight of Computations.
Bulletin of the EATCS, 1995

Response to the Essays "On Computational Complexity and the Nature of Computer Science".
ACM Comput. Surv., 1995

Turing Award Lecture: On Computational Complexity and the Nature of Computer Science.
ACM Comput. Surv., 1995

On the Computing Paradigm and Computational Complexity.
Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

1994
The Random Oracle Hypothesis Is False.
J. Comput. Syst. Sci., 1994

On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line.
J. Comput. Syst. Sci., 1994

About the Nature of the Computer Science.
Bulletin of the EATCS, 1994

Turing Award Lecture: On Computational Complexity and the Nature of Computer Science.
Commun. ACM, 1994

The Structure of the Complexity of Computations: A Guided Tour Through Complexity Classes.
Proceedings of the Technology and Foundations - Information Processing '94, Volume 1, Proceedings of the IFIP 13th World Computer Congress, Hamburg, Germany, 28 August, 1994

On the Intellectual Terrain Around NP.
Proceedings of the Algorithms and Complexity, Second Italian Conference, 1994

1993
On IP = PSPACE and Theorems with Narrow Proofs.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Some Observations about Relativization of Space Bounded Computations.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Relativization: a Revisionistic Retrospective.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Gödel, von Neumann and the P =? NP Problem.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

On the Importance of Being II2-Hard.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Collapsing Hierarchies.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Sparse Complete Sets for NP and the Optimal Collapse of the Polynomial Hierarchy.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

A Retrospective on Structural Complexity.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

Structural Complexity.
Proceedings of the Current Trends in Theoretical Computer Science - Essays and Tutorials, 1993

A Broader Research Agenda for Theory.
Bulletin of the EATCS, 1993

Some Observations About the Nature of Computer Science.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1993

Computing the Future: Whither Computer Science and Engineering?
Proceedings of the ACM 21th Conference on Computer Science, 1993

1992
Computing the Future - Comittee to Assess the Scope and Direction of Computer Science and Technology of the National Research Council.
Commun. ACM, 1992

1991
Space Bounded Computations: Review and New Separation Results.
Theor. Comput. Sci., 1991

One-Way Functions and the Nonisomorphism of NP-Complete Sets.
Theor. Comput. Sci., 1991

1990
Robust Machines Accept Easy Sets.
Theor. Comput. Sci., 1990

New Developments in Structural Complexity Theory.
Theor. Comput. Sci., 1990

On Unique Staisfiability and Randomized Reductions.
Bulletin of the EATCS, 1990

Structural Complexity Theory: recent Surprises.
Proceedings of the SWAT 90, 1990

1989
The Boolean Hierarchy II: Applications.
SIAM J. Comput., 1989

The Structural Complexity Column.
Bulletin of the EATCS, 1989

The Structural Complexity Column.
Bulletin of the EATCS, 1989

The Cornell Commission: On Morris and the Worm.
Commun. ACM, 1989

Space Bounded Computations: Review And New Separation Results.
Proceedings of the Mathematical Foundations of Computer Science 1989, 1989

The Complexity Of The Real Line Is A Fractal.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988
Complexity Classes without Machines: On Complete Languages for UP.
Theor. Comput. Sci., 1988

The Boolean Hierarchy I: Structural Properties.
SIAM J. Comput., 1988

On Sparse Oracles Separating Feasible Complexity Classes.
Inf. Process. Lett., 1988

The Structural Complexity Column.
Bulletin of the EATCS, 1988

New Developments in Structural Complexity Theory.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

1987
Structural Complexity Columns in Sparse complete sets for NP and the optimal collpase of the polynomial hierarchy.
Bulletin of the EATCS, 1987

The Structural Complexity Column.
Bulletin of the EATCS, 1987

Some Observations of NP Complete Sets.
Proceedings of the Fundamentals of Computation Theory, 1987

One-way functions, robustness, and the non-isomorphism of NP-complete sets.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

1986
On Sparse Oracles Separating Feasible Complexity Classes.
Proceedings of the STACS 86, 1986

Pragmatic Aspects of Complexity Theory (Panel).
IFIP Congress, 1986

Containment, Separation, Complete Sets, and Immunity of Complexity Classes.
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

Complexity Classes Without Machines: On Complete Languages for UP.
Proceedings of the Automata, Languages and Programming, 13th International Colloquium, 1986

1985
Independence Results About Context-Free Languages and Lower Bounds.
Inf. Process. Lett., 1985

Sparse Sets in NP-P: EXPTIME versus NEXPTIME
Information and Control, 1985

Solvable problems with conflicting relativizations.
Bulletin of the EATCS, 1985

On Complete Problems for NP$\cap$CoNP.
Proceedings of the Automata, 1985

1984
Computation Times of NP Sets of Different Densities.
Theor. Comput. Sci., 1984

On non-isomorphic NP complete sets.
Bulletin of the EATCS, 1984

1983
On Gödel Speed-Up and Succinctness of Language Representations.
Theor. Comput. Sci., 1983

On Sparse Sets in NP - P.
Inf. Process. Lett., 1983

Sparse Sets in NP-P: EXPTIME versus NEXPTIME
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Computation Times of NP Sets of Different Densities.
Proceedings of the Automata, 1983

Generalized Kolmogorov Complexity and the Structure of Feasible Computations (Preliminary Report)
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982
A Note on Natural Complete Sets and Gödel Numberings.
Theor. Comput. Sci., 1982

1981
Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata.
SIAM J. Comput., 1981

Observations About the Development of Theoretical Computer Science.
IEEE Annals of the History of Computing, 1981

1980
On the Succinctness of Different Representations of Languages.
SIAM J. Comput., 1980

An Eassay about Research on Sparse NP Complete Sets.
Proceedings of the Mathematical Foundations of Computer Science 1980 (MFCS'80), 1980

1979
Relations Between Diagonalization, Proof Systems, and Complexity Gaps.
Theor. Comput. Sci., 1979

Relative Succinctness of Representations of Languages and Separation of Complexity Classes.
Proceedings of the Mathematical Foundations of Computer Science 1979, 1979

On the Succintness of Different Representations of Languages.
Proceedings of the Automata, 1979

Observations about the Development of Theoretical Computer Science
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

Succinctness, Verifiability and Determinism in Representations of Polynomial-Time Languages
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978
On Log-Tape Isomorphisms of Complete Sets.
Theor. Comput. Sci., 1978

On Polynomial Time Isomorphisms of Some New Complete Sets.
J. Comput. Syst. Sci., 1978

One-Way Log-Tape Reductions
Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

1977
On Isomorphisms and Density of NP and Other Complete Sets.
SIAM J. Comput., 1977

On polynomial time isomorphisms of complete sets.
Proceedings of the Theoretical Computer Science, 1977

Relations Between Diagonalization, Proof Systems, and Complexity Gaps (Preliminary Version)
Proceedings of the 9th Annual ACM Symposium on Theory of Computing, 1977

1976
On Tape Bounds for Single Letter Alphabet Language Processing.
Theor. Comput. Sci., 1976

On Effective Speed-Up and Long Proofs of Trivial Theorems in Formal Theories.
ITA, 1976

On the Structure of Feasible Computations.
Advances in Computers, 1976

On Isomorphisms and Density of NP and Other Complete Sets
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

1975
On Simple Gödel Numberings and Translations.
SIAM J. Comput., 1975

Computational Complexity of Formal Translations.
Mathematical Systems Theory, 1975

A Note on Tape Bounds for SLA Language Processing
Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975

1974
On Simple Goedel Numberings and Translations.
Proceedings of the Automata, Languages and Programming, 2nd Colloquium, University of Saarbrücken, July 29, 1974

On the Structure of Feasible Computation.
Proceedings of the GI - 4. Jahrestagung, Berlin, 9.-12. Oktober 1974, 1974

On the Power of Multiplication in Random Access Machines
Proceedings of the 15th Annual Symposium on Switching and Automata Theory, 1974

1973
Group Theoretic Characterization of Linear Permutation Automata.
J. Comput. Syst. Sci., 1973

On the Problem of Finding Natural Computational Complexity Measures.
Proceedings of the Mathematical Foundations of Computer Science: Proceedings of Symposium and Summer School, 1973

1972
On Non-Determinancy in Simple Computing Devices.
Acta Inf., 1972

1971
Computational Complexity of Random Acess Stored Program Machines.
Mathematical Systems Theory, 1971

The use of Lists in the Study of Undecidable Problems in Automata Theory.
J. Comput. Syst. Sci., 1971

An Overview of the Theory of Computational Complexity.
J. ACM, 1971

Complexity of Formal Translations and Speed-Up Results
Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971

1970
R70-1 A Note on Computing Time for the Recognition of Context- Free Languages by a Single-Tape Turing Machine.
IEEE Trans. Computers, 1970

A Note on One-Way and Two-Way Automata.
Mathematical Systems Theory, 1970

What makes Some Language Theory Problems Undecidable.
J. Comput. Syst. Sci., 1970

1969
Two Memory Bounds for the Recognition of Primes by Automata.
Mathematical Systems Theory, 1969

On the Complexity of Undecidable Problems in Automata Theory.
J. ACM, 1969

Automata-based computational complexity.
Inf. Sci., 1969

1968
Tape-Reversal Bounded Turing Machine Computations.
J. Comput. Syst. Sci., 1968

On the Recognition of Primes by Automata.
J. ACM, 1968

Computational Complexity of One-Tape Turing Machine Computations.
J. ACM, 1968

Structure of Undecidable Problems in Automata Theory
Proceedings of the 9th Annual Symposium on Switching and Automata Theory, 1968

Tape Reversal Complexity Hierarchies
Proceedings of the 9th Annual Symposium on Switching and Automata Theory, 1968

1967
Homomorphic Images of Linear Sequential Machines.
J. Comput. Syst. Sci., 1967

On Memory Requirements for Context-Free Language Recognition.
J. ACM, 1967

On the Complexity of Undecidable Problems in Automata Theory
Proceedings of the 8th Annual Symposium on Switching and Automata Theory, 1967

1966
Minimal Feedback Realizations of Sequential Machines.
IEEE Trans. Electronic Computers, 1966

1965
Two Tests for the Linearity of Sequential Machines.
IEEE Trans. Electronic Computers, 1965

Hierarchies of memory limited computations
Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design, 1965

Memory bounds for recognition of context-free and context-sensitive languages
Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design, 1965

1964
Pair Algebra and Its Application to Automata Theory
Information and Control, December, 1964

On the application of pair algebra to automata theory
Proceedings of the 5th Annual Symposium on Switching Circuit Theory and Logical Design, 1964

Computational complexity of recursive sequences
Proceedings of the 5th Annual Symposium on Switching Circuit Theory and Logical Design, 1964

1963
Regularity Preserving Modifications of Regular Expressions
Information and Control, March, 1963

A Study of Feedback and Errors in Sequential Machines.
IEEE Trans. Electronic Computers, 1963

Further Results on the Structure of Sequential Machines.
J. ACM, 1963

1962
Some Dangers in State Reduction of Sequential Machines
Information and Control, September, 1962

Loop-Free Structure of Sequential Machines
Information and Control, March, 1962

Maximal Autonomous Clocks of Sequential Machines.
IRE Trans. Electronic Computers, 1962

1961
On the State Assignment Problem for Sequential Machines II.
IRE Trans. Electronic Computers, 1961

On the State Assignment Problem for Sequential Machines. I.
IRE Trans. Electronic Computers, 1961

1960
Symbolic Analysis of a Decomposition of Information Processing Machines
Information and Control, June, 1960

1959
The Applications of Some Basic Inequalities for Entropy
Information and Control, September, 1959


  Loading...