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

  • 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.
  • Godel, von Neumann and the P=?NP Problem 

    Hartmanis, Juris (Cornell University, 1989-04)
    In a 1956 letter, Godel asked von Neumann about the computational complexity of an NP complete problem. In this column, we review the historic setting of this period, discuss Godel's amazing letter and why von Neumann ...
  • On the Importance of Being II2-Hard 

    Hartmanis, Juris (Cornell University, 1989-01)
    In this column, we show how a variety of interesting results in theory of computation all follow from a simple observation about $\prod _{2}$-complete sets of total machines. We easily derive: a) representation independent ...
  • Space Bounded Computations: Review And New Separation Results 

    Hartmanis, Juris; Ranjan, Desh (Cornell University, 1989-05)
    In this paper, we review the key results about space bounded complexity classes, discuss the central open problems and outline the relevant proof techniques. We show that, for a slightly modified Turing machine model, ...
  • Structural Complexity Column: Some Observations About Relativization of Space Bounded Computations 

    Hartmanis, Juris (Cornell University, 1988-05)
    NO ABSTRACT AVAILABLE
  • New Developments in Structural Complexity Theory 

    Hartmanis, Juris (Cornell University, 1988-04)
    This paper discusses the scope and goals of structural complexity theory, describes some working hypothesis of this field and summarizes (some) recent development.
  • The Collapsing Hierarchies 

    Hartmanis, Juris (Cornell University, 1987-09)
    No Abstract Available
  • Structural Complexity Column for the Bulletin of the European Association for Theoretical Computer Science 

    Hartmanis, Juris (Cornell University, 1987-06)
    Abstract not Available
  • Some Observations About NP Complete Sets 

    Hartmanis, Juris (Cornell University, 1987-03)
    In this paper we summarize and extend some recent results about the properties of NP complete sets and related results about the structure of feasible computations.
  • One-Way Functions, Robustness, and the Non-Isomorphism of NP-Complete Sets 

    Hartmanis, Juris; Hemachandra, Lane A. (Cornell University, 1986-01)
    This paper 1. gives a relativized counterexample to the conjectured connection between the existence of one-way functions and the existence of non-isomorphic NP-complete sets. 2. establishes that in relativized worlds ...
  • Complexity Classes Without Machines: On Complete Languages for UP 

    Hartmanis, Juris; Hemachandra, Lane A. (Cornell University, 1986-04)
    This paper develops techniques for studying complexity classes that are not covered by known recursive enumerations of machines. Often, counting classes, probabilistic classes, and intersection classes lack such enumerations. ...
  • Relations Between Diagonalization, Proof Systems, and Complexity Gaps 

    Hartmanis, Juris (Cornell University, 1977-06)
    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. ...

View more

Statistics

RSS Feeds