This collection is intended to bring together in one place materials dealing with the work and legacy of Cornell Professor, Juris Hartmanis, both new materials and those published in other collections in eCommons.

Included here are:

  • A Conversation with Juris Hartmanis - Video and Multimedia Presentation
  • Papers by Juris Hartmanis

Recent Submissions

  • A Conversation with Juris Hartmanis 

    Hartmanis, Juris (Internet-First University Press, 2010-03-31)
    Juris Hartmanis is video taped in a far-reaching conversation (70 minutes) with colleague David Gries. They discuss Hartmanis’ childhood and family background and his immigration to the United States. Next they trace his ...
  • Relative Succinctness of Representations of Languages and Separation of Complexity Classes 

    Hartmanis, Juris (Cornell University, 1978-08)
    In this paper we study the relative succinctness of different representations of polymomial time languages and investigate what can and cannot be formally verified about these representations. We also show that the ...
  • One-Way Log-Tape Reductions 

    Hartmanis, Juris; Immerman, Neil; Mahaney, Stephen R. (Cornell University, 1978-07)
    One-way log-tape (1-L) reductions are mappings defined by log-tape Turing machines whose read head on the input can only move to the right. The 1-L reductions provide a more refined tool for studying the feasible complexity ...
  • On the Succintness of Different Representations of Languages 

    Hartmanis, Juris (Cornell University, 1978-06)
    The purpose of this paper is to give simple new proofs of some interesting recent results about the relative succintness of different representations of regular, deterministic and unambiguous context-free languages and ...
  • On Log-Tape Isomorphisms of Complete Sets 

    Hartmanis, Juris (Cornell University, 1977-07)
    In this paper we study $\log n$-tape computable reductions between sets and investigate conditions under which $\log n$-tape reductions between sets can be extended to $\log n$-tape computable isomorphisms of these sets. ...
  • On Polynomial Time Isomorphism of Complete Sets 

    Berman, L.; Hartmanis, Juris (Cornell University, 1976-12)
    IN this note we show that the recently discovered NP complete sets arising in number theory, the PTAPE complete sets arising in game theory and EXPTAPE complete sets arising from algebraic word problems are polynomial ...
  • On Isomorphisms and Density of NP and Other Complete Sets 

    Hartmanis, Juris; Berman, L. (Cornell University, 1975-10)
    If all NP complete sets are isomorphic under deterministic polynomial time mappings (p-isomorphic) then P $\neq$ NP and if all PTAPE complete sets are p-isomorphic then P $\neq$ PTAPE. We show that all NP complete sets ...
  • Relations Between Diagonalization, Proof Systems, and Complexity Gaps 

    Hartmanis, Juris (Cornell University, 1977-03)
    In this paper we study diagonal processes over time-bounded computations of one-tape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. ...
  • A Note on Tape Bounds for SLA Language Processing 

    Hartmanis, Juris; Berman, L. (Cornell University, 1975-05)
    In this note we show that the tape bounded complexity classes of languages over single letter alphabets are closed under complementation. We then use this result to show that there exists an infinite hierarchy of tape ...
  • Structural Complexity Theory: Recent Surprises 

    Hartmanis, Juris; Chang, Richard; Ranjan, Desh; Rohatgi, Pankaj (Cornell University, 1990-04)
    This paper reviews the impact of some recent results on the research paradigms in structural complexity theory.

View more


RSS Feeds