Juris Hartmanis

135 papers A* 18A 1B 6C 2Misc 1Journal 77Unranked 19
YearRankTypeTitle / Venue / Authors
2012 — conf
The Turing Computational Model.
ACM-TURING
Juris Hartmanis, Stephen Cook, William Kahan, Richard Edwin Stearns, Andrew C. Yao
2012 C conf
Turing Machine-Inspired Computer Science Results.
CiE
Juris Hartmanis
2003 J jnl
Separation of complexity classes.
J. ACM
Juris Hartmanis
2002 — conf
The Separation Problems and Descriptional Complexity.
DCFS
Juris Hartmanis
2001 Misc conf
Computational Complexity and Mathematical Proofs.
Informatics
Juris Hartmanis
2000 — ch.
Undecidability and Incompleteness Results in Automata Theory.
A Half-Century of Automata Theory
Juris Hartmanis
1999 A* conf
Observations about the Nature and State of Computer Science (Keynote Address).
ICALP
Juris Hartmanis
1998 J jnl
Innovation and Obstacles: The Future of Computing.
Computer
David D. Clark, Edward A. Feigenbaum, Donald P. Greenberg, Juris Hartmanis, Robert W. Lucky, Robert Metcalfe, Raj Reddy, Mary Shaw, William A. Wulf
1995 B conf
On the Computing Paradigm and Computational Complexity.
MFCS
Juris Hartmanis
1995 J jnl
On the Weight of Computations.
Bull. EATCS
Juris Hartmanis
1995 J jnl
Response to the Essays "On Computational Complexity and the Nature of Computer Science".
ACM Comput. Surv.
Juris Hartmanis
1995 J jnl
Turing Award Lecture: On Computational Complexity and the Nature of Computer Science.
ACM Comput. Surv.
Juris Hartmanis
1994 J jnl
About the Nature of the Computer Science.
Bull. EATCS
Juris Hartmanis
1994 J jnl
On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line.
J. Comput. Syst. Sci.
Jin-Yi Cai, Juris Hartmanis
1994 C conf
On the Intellectual Terrain Around NP.
CIAC
Juris Hartmanis, Suresh Chari
1994 J jnl
The Random Oracle Hypothesis Is False.
J. Comput. Syst. Sci.
Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, Pankaj Rohatgi
1994 — conf
The Structure of the Complexity of Computations: A Guided Tour Through Complexity Classes.
IFIP Congress (1)
Juris Hartmanis
1994 J jnl
Turing Award Lecture: On Computational Complexity and the Nature of Computer Science.
Commun. ACM
Juris Hartmanis
1993 J jnl
A Broader Research Agenda for Theory.
Bull. EATCS
Juris Hartmanis
1993 — ch.
A Retrospective on Structural Complexity.
Current Trends in Theoretical Computer Science
Juris Hartmanis
1993 — ch.
Collapsing Hierarchies.
Current Trends in Theoretical Computer Science
Juris Hartmanis
1993 — conf
Computing the Future: Whither Computer Science and Engineering?
ACM Conference on Computer Science
Herbert S. Lin, Juris Hartmanis, John R. Rice, Morton Lowengrub
1993 — ch.
Gödel, von Neumann and the P =? NP Problem.
Current Trends in Theoretical Computer Science
Juris Hartmanis
1993 — ch.
On IP = PSPACE and Theorems with Narrow Proofs.
Current Trends in Theoretical Computer Science
Juris Hartmanis, Richard Chang, Desh Ranjan, Pankaj Rohatgi
1993 — ch.
On the Importance of Being II
Current Trends in Theoretical Computer Science
Juris Hartmanis
1993 — ch.
Relativization: a Revisionistic Retrospective.
Current Trends in Theoretical Computer Science
Juris Hartmanis, Richard Chang, Suresh Chari, Desh Ranjan, Pankaj Rohatgi
1993 — conf
Some Observations About the Nature of Computer Science.
FSTTCS
Juris Hartmanis
1993 — ch.
Some Observations about Relativization of Space Bounded Computations.
Current Trends in Theoretical Computer Science
Juris Hartmanis, Richard Chang, Jim Kadin, Stephen G. Mitchell
1993 — ch.
Sparse Complete Sets for NP and the Optimal Collapse of the Polynomial Hierarchy.
Current Trends in Theoretical Computer Science
Juris Hartmanis
1993 — ch.
Structural Complexity.
Current Trends in Theoretical Computer Science
Juris Hartmanis
1992 J jnl
Computing the Future - Comittee to Assess the Scope and Direction of Computer Science and Technology of the National Research Council.
Commun. ACM
Juris Hartmanis
1991 J jnl
One-Way Functions and the Nonisomorphism of NP-Complete Sets.
Theor. Comput. Sci.
Juris Hartmanis, Lane A. Hemachandra
1991 J jnl
Space Bounded Computations: Review and New Separation Results.
Theor. Comput. Sci.
Desh Ranjan, Richard Chang, Juris Hartmanis
1990 J jnl
New Developments in Structural Complexity Theory.
Theor. Comput. Sci.
Juris Hartmanis
1990 J jnl
On Unique Staisfiability and Randomized Reductions.
Bull. EATCS
Juris Hartmanis, Richard Chang, Desh Ranjan, Pankaj Rohatgi
1990 J jnl
Robust Machines Accept Easy Sets.
Theor. Comput. Sci.
Juris Hartmanis, Lane A. Hemachandra
1990 — conf
Structural Complexity Theory: recent Surprises.
SWAT
Juris Hartmanis, Richard Chang, Desh Ranjan, Pankaj Rohatgi
1989 — book
Feasible computations and provable complexity properties.
Juris Hartmanis
1989 B conf
Space Bounded Computations: Review And New Separation Results.
MFCS
Juris Hartmanis, Desh Ranjan
1989 J jnl
The Boolean Hierarchy II: Applications.
SIAM J. Comput.
Jin-Yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung
1989 — conf
The Complexity Of The Real Line Is A Fractal.
SCT
Jin-Yi Cai, Juris Hartmanis
1989 J jnl
The Cornell Commission: On Morris and the Worm.
Commun. ACM
Ted Eisenberg, David Gries, Juris Hartmanis, Don Holcomb, M. Stuart Lynn, Thomas Santoro
1989 J jnl
The Structural Complexity Column.
Bull. EATCS
Juris Hartmanis
1989 J jnl
The Structural Complexity Column.
Bull. EATCS
Juris Hartmanis
1988 J jnl
Complexity Classes without Machines: On Complete Languages for UP.
Theor. Comput. Sci.
Juris Hartmanis, Lane A. Hemachandra
1988 A* conf
New Developments in Structural Complexity Theory.
ICALP
Juris Hartmanis
1988 J jnl
On Sparse Oracles Separating Feasible Complexity Classes.
Inf. Process. Lett.
Juris Hartmanis, Lane A. Hemachandra
1988 J jnl
The Boolean Hierarchy I: Structural Properties.
SIAM J. Comput.
Jin-Yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung
1988 J jnl
The Structural Complexity Column.
Bull. EATCS
Juris Hartmanis
1987 — conf
One-way functions, robustness, and the non-isomorphism of NP-complete sets.
SCT
Juris Hartmanis, Lane A. Hemachandra
1987 B conf
Some Observations of NP Complete Sets.
FCT
Juris Hartmanis
1987 J jnl
Structural Complexity Columns in Sparse complete sets for NP and the optimal collpase of the polynomial hierarchy.
Bull. EATCS
Juris Hartmanis
1987 J jnl
The Structural Complexity Column.
Bull. EATCS
Juris Hartmanis
1986 A* conf
Complexity Classes Without Machines: On Complete Languages for UP.
ICALP
Juris Hartmanis, Lane A. Hemachandra
1986 A* conf
Containment, Separation, Complete Sets, and Immunity of Complexity Classes.
ICALP
Juris Hartmanis, Ming Li, Yaacov Yesha
1986 A conf
On Sparse Oracles Separating Feasible Complexity Classes.
STACS
Juris Hartmanis, Lane A. Hemachandra
1986 — conf
Pragmatic Aspects of Complexity Theory (Panel).
IFIP Congress
Juris Hartmanis
1986 A* ed.
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA
STOC
Juris Hartmanis
1985 J jnl
Independence Results About Context-Free Languages and Lower Bounds.
Inf. Process. Lett.
Juris Hartmanis
1985 A* conf
On Complete Problems for NP$\cap$CoNP.
ICALP
Juris Hartmanis, Neil Immerman
1985 J jnl
Solvable problems with conflicting relativizations.
Bull. EATCS
Juris Hartmanis
1985 J jnl
Sparse Sets in NP-P: EXPTIME versus NEXPTIME
Inf. Control.
Juris Hartmanis, Neil Immerman, Vivian Sewelson
1984 J jnl
Computation Times of NP Sets of Different Densities.
Theor. Comput. Sci.
Juris Hartmanis, Yaacov Yesha
1984 J jnl
On non-isomorphic NP complete sets.
Bull. EATCS
Juris Hartmanis
1983 A* conf
Computation Times of NP Sets of Different Densities.
ICALP
Juris Hartmanis, Yaacov Yesha
1983 A* conf
Generalized Kolmogorov Complexity and the Structure of Feasible Computations (Preliminary Report)
FOCS
Juris Hartmanis
1983 J jnl
On Gödel Speed-Up and Succinctness of Language Representations.
Theor. Comput. Sci.
Juris Hartmanis
1983 J jnl
On Sparse Sets in NP - P.
Inf. Process. Lett.
Juris Hartmanis
1983 A* conf
Sparse Sets in NP-P: EXPTIME versus NEXPTIME
STOC
Juris Hartmanis, Vivian Sewelson, Neil Immerman
1982 J jnl
A Note on Natural Complete Sets and Gödel Numberings.
Theor. Comput. Sci.
Juris Hartmanis
1981 J jnl
Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata.
SIAM J. Comput.
Juris Hartmanis, Stephen R. Mahaney
1981 J jnl
Observations About the Development of Theoretical Computer Science.
IEEE Ann. Hist. Comput.
Juris Hartmanis
1980 B conf
An Eassay about Research on Sparse NP Complete Sets.
MFCS
Juris Hartmanis, Stephen R. Mahaney
1980 J jnl
On the Succinctness of Different Representations of Languages.
SIAM J. Comput.
Juris Hartmanis
1979 A* conf
Observations about the Development of Theoretical Computer Science
FOCS
Juris Hartmanis
1979 A* conf
On the Succintness of Different Representations of Languages.
ICALP
Juris Hartmanis
1979 J jnl
Relations Between Diagonalization, Proof Systems, and Complexity Gaps.
Theor. Comput. Sci.
Juris Hartmanis
1979 B conf
Relative Succinctness of Representations of Languages and Separation of Complexity Classes.
MFCS
Juris Hartmanis, Theodore P. Baker
1979 A* conf
Succinctness, Verifiability and Determinism in Representations of Polynomial-Time Languages
FOCS
Theodore P. Baker, Juris Hartmanis
1978 J jnl
On Log-Tape Isomorphisms of Complete Sets.
Theor. Comput. Sci.
Juris Hartmanis
1978 J jnl
On Polynomial Time Isomorphisms of Some New Complete Sets.
J. Comput. Syst. Sci.
Juris Hartmanis, Leonard Berman
1978 A* conf
One-Way Log-Tape Reductions
FOCS
Juris Hartmanis, Neil Immerman, Stephen R. Mahaney
1977 J jnl
On Isomorphisms and Density of NP and Other Complete Sets.
SIAM J. Comput.
Leonard Berman, Juris Hartmanis
1977 — conf
On polynomial time isomorphisms of complete sets.
Theoretical Computer Science
Leonard Berman, Juris Hartmanis
1977 A* conf
Relations Between Diagonalization, Proof Systems, and Complexity Gaps (Preliminary Version)
STOC
Juris Hartmanis
1976 J jnl
Independence results in computer science.
SIGACT News
Juris Hartmanis, John E. Hopcroft
1976 J jnl
On Effective Speed-Up and Long Proofs of Trivial Theorems in Formal Theories.
RAIRO Theor. Informatics Appl.
Juris Hartmanis
1976 A* conf
On Isomorphisms and Density of NP and Other Complete Sets
STOC
Juris Hartmanis, Leonard Berman
1976 J jnl
On Tape Bounds for Single Letter Alphabet Language Processing.
Theor. Comput. Sci.
Juris Hartmanis, Leonard Berman
1976 J jnl
On the Structure of Feasible Computations.
Adv. Comput.
Juris Hartmanis, Janos Simon
1975 A* conf
A Note on Tape Bounds for SLA Language Processing
FOCS
Juris Hartmanis, Leonard Berman
1975 J jnl
Computational Complexity of Formal Translations.
Math. Syst. Theory
Juris Hartmanis
1975 J jnl
On Simple Gödel Numberings and Translations.
SIAM J. Comput.
Juris Hartmanis, Theodore P. Baker
1974 A* conf
On Simple Goedel Numberings and Translations.
ICALP
Juris Hartmanis, Theodore P. Baker
1974 — conf
On the Power of Multiplication in Random Access Machines
SWAT
Juris Hartmanis, Janos Simon
1974 — conf
On the Structure of Feasible Computation.
GI Jahrestagung
Juris Hartmanis, Janos Simon
1973 J jnl
Group Theoretic Characterization of Linear Permutation Automata.
J. Comput. Syst. Sci.
Juris Hartmanis, H. Walter
1973 B conf
On the Problem of Finding Natural Computational Complexity Measures.
MFCS
Juris Hartmanis
1972 J jnl
On Non-Determinancy in Simple Computing Devices.
Acta Informatica
Juris Hartmanis
1971 J jnl
An Overview of the Theory of Computational Complexity.
J. ACM
Juris Hartmanis, John E. Hopcroft
1971 A* conf
Complexity of Formal Translations and Speed-Up Results
STOC
Robert L. Constable, Juris Hartmanis
1971 J jnl
Computational Complexity of Random Acess Stored Program Machines.
Math. Syst. Theory
Juris Hartmanis
1971 J jnl
The use of Lists in the Study of Undecidable Problems in Automata Theory.
J. Comput. Syst. Sci.
Juris Hartmanis, Forbes D. Lewis
1970 J jnl
A Note on One-Way and Two-Way Automata.
Math. Syst. Theory
Juris Hartmanis
1970 J jnl
Computer science and mathematics.
ACM SIGCSE Bull.
George E. Forsythe, Bernard A. Galler, Juris Hartmanis, Alan J. Perlis, Joseph F. Traub
1970 J jnl
R70-1 A Note on Computing Time for the Recognition of Context- Free Languages by a Single-Tape Turing Machine.
IEEE Trans. Computers
Juris Hartmanis
1970 J jnl
What makes Some Language Theory Problems Undecidable.
J. Comput. Syst. Sci.
Juris Hartmanis, John E. Hopcroft
1969 J jnl
Automata-based computational complexity.
Inf. Sci.
Juris Hartmanis, Richard Edwin Stearns
1969 J jnl
On the Complexity of Undecidable Problems in Automata Theory.
J. ACM
Juris Hartmanis
1969 J jnl
Two Memory Bounds for the Recognition of Primes by Automata.
Math. Syst. Theory
Juris Hartmanis, H. Shank
1968 J jnl
Computational Complexity of One-Tape Turing Machine Computations.
J. ACM
Juris Hartmanis
1968 J jnl
On the Recognition of Primes by Automata.
J. ACM
Juris Hartmanis, H. Shank
1968 — conf
Structure of Undecidable Problems in Automata Theory
SWAT
Juris Hartmanis, John E. Hopcroft
1968 — conf
Tape Reversal Complexity Hierarchies
SWAT
Patrick C. Fischer, Juris Hartmanis, Manuel Blum
1968 J jnl
Tape-Reversal Bounded Turing Machine Computations.
J. Comput. Syst. Sci.
Juris Hartmanis
1967 J jnl
Homomorphic Images of Linear Sequential Machines.
J. Comput. Syst. Sci.
Juris Hartmanis, Wayne A. Davis
1967 J jnl
On Memory Requirements for Context-Free Language Recognition.
J. ACM
Juris Hartmanis
1967 — conf
On the Complexity of Undecidable Problems in Automata Theory
SWAT
Juris Hartmanis
1966 J jnl
Minimal Feedback Realizations of Sequential Machines.
IEEE Trans. Electron. Comput.
Juris Hartmanis
1965 — conf
Hierarchies of memory limited computations
SWCT
Richard Edwin Stearns, Juris Hartmanis, Philip M. Lewis II
1965 — conf
Memory bounds for recognition of context-free and context-sensitive languages
SWCT
Philip M. Lewis II, Richard Edwin Stearns, Juris Hartmanis
1965 J jnl
Two Tests for the Linearity of Sequential Machines.
IEEE Trans. Electron. Comput.
Juris Hartmanis
1964 — conf
Computational complexity of recursive sequences
SWCT
Juris Hartmanis, Richard Edwin Stearns
1964 — conf
On the application of pair algebra to automata theory
SWCT
Richard Edwin Stearns, Juris Hartmanis
1964 J jnl
Pair Algebra and Its Application to Automata Theory
Inf. Control.
Juris Hartmanis, Richard Edwin Stearns
1963 J jnl
A Study of Feedback and Errors in Sequential Machines.
IEEE Trans. Electron. Comput.
Juris Hartmanis, Richard Edwin Stearns
1963 J jnl
Further Results on the Structure of Sequential Machines.
J. ACM
Juris Hartmanis
1963 J jnl
Regularity Preserving Modifications of Regular Expressions
Inf. Control.
Richard Edwin Stearns, Juris Hartmanis
1962 J jnl
Loop-Free Structure of Sequential Machines
Inf. Control.
Juris Hartmanis
1962 J jnl
Maximal Autonomous Clocks of Sequential Machines.
IRE Trans. Electron. Comput.
Juris Hartmanis
1962 J jnl
Some Dangers in State Reduction of Sequential Machines
Inf. Control.
Juris Hartmanis, Richard Edwin Stearns
1961 J jnl
On the State Assignment Problem for Sequential Machines II.
IRE Trans. Electron. Comput.
Richard Edwin Stearns, Juris Hartmanis
1961 J jnl
On the State Assignment Problem for Sequential Machines. I.
IRE Trans. Electron. Comput.
Juris Hartmanis
1960 J jnl
Symbolic Analysis of a Decomposition of Information Processing Machines
Inf. Control.
Juris Hartmanis
1959 J jnl
The Applications of Some Basic Inequalities for Entropy
Inf. Control.
Juris Hartmanis