default search action
Juris Hartmanis
Person information
- award: Turing Award, 1993
- award: ACM Distinguished Service Award, 2013
- affiliation: Cornell University, Ithaca, NY, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2010 – 2019
- 2012
- [c46]Juris Hartmanis, Stephen Cook, William Kahan, Richard Edwin Stearns, Andrew C. Yao:
The Turing Computational Model. ACM-TURING 2012: 8:1 - [c45]Juris Hartmanis:
Turing Machine-Inspired Computer Science Results. CiE 2012: 276-282
2000 – 2009
- 2003
- [j77]Juris Hartmanis:
Separation of complexity classes. J. ACM 50(1): 58-62 (2003) - 2002
- [c44]Juris Hartmanis:
The Separation Problems and Descriptional Complexity. DCFS 2002: 35 - 2001
- [c43]Juris Hartmanis:
Computational Complexity and Mathematical Proofs. Informatics 2001: 251-256 - 2000
- [p10]Juris Hartmanis:
Undecidability and Incompleteness Results in Automata Theory. A Half-Century of Automata Theory 2000: 21-35
1990 – 1999
- 1999
- [c42]Juris Hartmanis:
Observations about the Nature and State of Computer Science (Keynote Address). ICALP 1999: 105 - 1998
- [j76]David D. Clark, Edward A. Feigenbaum, Donald P. Greenberg, Juris Hartmanis, Robert W. Lucky, Robert Metcalfe, Raj Reddy, Mary Shaw, William A. Wulf:
Innovation and Obstacles: The Future of Computing. Computer 31: 29-38 (1998) - 1995
- [j75]Juris Hartmanis:
Turing Award Lecture: On Computational Complexity and the Nature of Computer Science. ACM Comput. Surv. 27(1): 7-16 (1995) - [j74]Juris Hartmanis:
Response to the Essays "On Computational Complexity and the Nature of Computer Science". ACM Comput. Surv. 27(1): 59-61 (1995) - [j73]Juris Hartmanis:
On the Weight of Computations. Bull. EATCS 55 (1995) - [c41]Juris Hartmanis:
On the Computing Paradigm and Computational Complexity. MFCS 1995: 82-92 - 1994
- [j72]Juris Hartmanis:
Turing Award Lecture: On Computational Complexity and the Nature of Computer Science. Commun. ACM 37(10): 37-43 (1994) - [j71]Juris Hartmanis:
About the Nature of the Computer Science. Bull. EATCS 53: 170-190 (1994) - [j70]Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, Pankaj Rohatgi:
The Random Oracle Hypothesis Is False. J. Comput. Syst. Sci. 49(1): 24-39 (1994) - [j69]Jin-yi Cai, Juris Hartmanis:
On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line. J. Comput. Syst. Sci. 49(3): 605-619 (1994) - [c40]Juris Hartmanis, Suresh Chari:
On the Intellectual Terrain Around NP. CIAC 1994: 1-11 - [c39]Juris Hartmanis:
The Structure of the Complexity of Computations: A Guided Tour Through Complexity Classes. IFIP Congress (1) 1994: 213-220 - 1993
- [j68]Juris Hartmanis:
A Broader Research Agenda for Theory. Bull. EATCS 49: 125-129 (1993) - [c38]Herbert S. Lin, Juris Hartmanis, John R. Rice, Morton Lowengrub:
Computing the Future: Whither Computer Science and Engineering? ACM Conference on Computer Science 1993: 530 - [c37]Juris Hartmanis:
Some Observations About the Nature of Computer Science. FSTTCS 1993: 1-12 - [p9]Juris Hartmanis:
Structural Complexity. Current Trends in Theoretical Computer Science 1993: 395-396 - [p8]Juris Hartmanis:
A Retrospective on Structural Complexity. Current Trends in Theoretical Computer Science 1993: 397-402 - [p7]Juris Hartmanis:
Sparse Complete Sets for NP and the Optimal Collapse of the Polynomial Hierarchy. Current Trends in Theoretical Computer Science 1993: 403-411 - [p6]Juris Hartmanis:
Collapsing Hierarchies. Current Trends in Theoretical Computer Science 1993: 412-422 - [p5]Juris Hartmanis, Richard Chang, Jim Kadin, Stephen G. Mitchell:
Some Observations about Relativization of Space Bounded Computations. Current Trends in Theoretical Computer Science 1993: 423-434 - [p4]Juris Hartmanis:
On the Importance of Being II2-Hard. Current Trends in Theoretical Computer Science 1993: 435-444 - [p3]Juris Hartmanis:
Gödel, von Neumann and the P =? NP Problem. Current Trends in Theoretical Computer Science 1993: 445-450 - [p2]Juris Hartmanis, Richard Chang, Desh Ranjan, Pankaj Rohatgi:
On IP = PSPACE and Theorems with Narrow Proofs. Current Trends in Theoretical Computer Science 1993: 484-493 - [p1]Juris Hartmanis, Richard Chang, Suresh Chari, Desh Ranjan, Pankaj Rohatgi:
Relativization: a Revisionistic Retrospective. Current Trends in Theoretical Computer Science 1993: 537-548 - 1992
- [j67]Juris Hartmanis:
Computing the Future - Comittee to Assess the Scope and Direction of Computer Science and Technology of the National Research Council. Commun. ACM 35(11): 30-40 (1992) - 1991
- [j66]Desh Ranjan, Richard Chang, Juris Hartmanis:
Space Bounded Computations: Review and New Separation Results. Theor. Comput. Sci. 80(2): 289-302 (1991) - [j65]Juris Hartmanis, Lane A. Hemachandra:
One-Way Functions and the Nonisomorphism of NP-Complete Sets. Theor. Comput. Sci. 81(1): 155-163 (1991) - 1990
- [j64]Juris Hartmanis, Richard Chang, Desh Ranjan, Pankaj Rohatgi:
On Unique Staisfiability and Randomized Reductions. Bull. EATCS 41: 166-174 (1990) - [j63]Juris Hartmanis:
New Developments in Structural Complexity Theory. Theor. Comput. Sci. 71(1): 79-93 (1990) - [j62]Juris Hartmanis, Lane A. Hemachandra:
Robust Machines Accept Easy Sets. Theor. Comput. Sci. 74(2): 217-225 (1990) - [c36]Juris Hartmanis, Richard Chang, Desh Ranjan, Pankaj Rohatgi:
Structural Complexity Theory: recent Surprises. SWAT 1990: 1-12
1980 – 1989
- 1989
- [b1]Juris Hartmanis:
Feasible computations and provable complexity properties. CBMS-NSF regional conference series in applied mathematics 30, SIAM 1989, ISBN 978-0-89871-027-4, pp. 1-62 - [j61]Ted Eisenberg, David Gries, Juris Hartmanis, Don Holcomb, M. Stuart Lynn, Thomas Santoro:
The Cornell Commission: On Morris and the Worm. Commun. ACM 32(6): 706-709 (1989) - [j60]Juris Hartmanis:
The Structural Complexity Column. Bull. EATCS 37: 117-126 (1989) - [j59]Juris Hartmanis:
The Structural Complexity Column. Bull. EATCS 38: 101-106 (1989) - [j58]Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung:
The Boolean Hierarchy II: Applications. SIAM J. Comput. 18(1): 95-111 (1989) - [c35]Jin-yi Cai, Juris Hartmanis:
The Complexity Of The Real Line Is A Fractal. SCT 1989: 138-146 - [c34]Juris Hartmanis, Desh Ranjan:
Space Bounded Computations: Review And New Separation Results. MFCS 1989: 49-66 - 1988
- [j57]Juris Hartmanis:
The Structural Complexity Column. Bull. EATCS 35: 82-91 (1988) - [j56]Juris Hartmanis, Lane A. Hemachandra:
On Sparse Oracles Separating Feasible Complexity Classes. Inf. Process. Lett. 28(6): 291-295 (1988) - [j55]Jin-yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus W. Wagner, Gerd Wechsung:
The Boolean Hierarchy I: Structural Properties. SIAM J. Comput. 17(6): 1232-1252 (1988) - [j54]Juris Hartmanis, Lane A. Hemachandra:
Complexity Classes without Machines: On Complete Languages for UP. Theor. Comput. Sci. 58: 129-142 (1988) - [c33]Juris Hartmanis:
New Developments in Structural Complexity Theory. ICALP 1988: 271-286 - 1987
- [j53]Juris Hartmanis:
Structural Complexity Columns in Sparse complete sets for NP and the optimal collpase of the polynomial hierarchy. Bull. EATCS 32: 73-81 (1987) - [j52]Juris Hartmanis:
The Structural Complexity Column. Bull. EATCS 33: 26-39 (1987) - [c32]Juris Hartmanis, Lane A. Hemachandra:
One-way functions, robustness, and the non-isomorphism of NP-complete sets. SCT 1987: 160-174 - [c31]Juris Hartmanis:
Some Observations of NP Complete Sets. FCT 1987: 185-196 - 1986
- [c30]Juris Hartmanis, Lane A. Hemachandra:
Complexity Classes Without Machines: On Complete Languages for UP. ICALP 1986: 123-135 - [c29]Juris Hartmanis, Ming Li, Yaacov Yesha:
Containment, Separation, Complete Sets, and Immunity of Complexity Classes. ICALP 1986: 136-145 - [c28]Juris Hartmanis:
Pragmatic Aspects of Complexity Theory (Panel). IFIP Congress 1986: 3-4 - [c27]Juris Hartmanis, Lane A. Hemachandra:
On Sparse Oracles Separating Feasible Complexity Classes. STACS 1986: 321-333 - [e1]Juris Hartmanis:
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA. ACM 1986, ISBN 0-89791-193-8 [contents] - 1985
- [j51]Juris Hartmanis:
Solvable problems with conflicting relativizations. Bull. EATCS 27: 40-48 (1985) - [j50]Juris Hartmanis, Neil Immerman, Vivian Sewelson:
Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Inf. Control. 65(2/3): 158-181 (1985) - [j49]Juris Hartmanis:
Independence Results About Context-Free Languages and Lower Bounds. Inf. Process. Lett. 20(5): 241-248 (1985) - [c26]Juris Hartmanis, Neil Immerman:
On Complete Problems for NP$\cap$CoNP. ICALP 1985: 250-259 - 1984
- [j48]Juris Hartmanis:
On non-isomorphic NP complete sets. Bull. EATCS 24: 73-77 (1984) - [j47]Juris Hartmanis, Yaacov Yesha:
Computation Times of NP Sets of Different Densities. Theor. Comput. Sci. 34: 17-32 (1984) - 1983
- [j46]Juris Hartmanis:
On Sparse Sets in NP - P. Inf. Process. Lett. 16(2): 55-60 (1983) - [j45]Juris Hartmanis:
On Gödel Speed-Up and Succinctness of Language Representations. Theor. Comput. Sci. 26: 335-342 (1983) - [c25]Juris Hartmanis:
Generalized Kolmogorov Complexity and the Structure of Feasible Computations (Preliminary Report). FOCS 1983: 439-445 - [c24]Juris Hartmanis, Yaacov Yesha:
Computation Times of NP Sets of Different Densities. ICALP 1983: 319-330 - [c23]Juris Hartmanis, Vivian Sewelson, Neil Immerman:
Sparse Sets in NP-P: EXPTIME versus NEXPTIME. STOC 1983: 382-391 - 1982
- [j44]Juris Hartmanis:
A Note on Natural Complete Sets and Gödel Numberings. Theor. Comput. Sci. 17: 75-89 (1982) - 1981
- [j43]Juris Hartmanis:
Observations About the Development of Theoretical Computer Science. IEEE Ann. Hist. Comput. 3(1): 42-51 (1981) - [j42]Juris Hartmanis, Stephen R. Mahaney:
Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata. SIAM J. Comput. 10(2): 383-390 (1981) - 1980
- [j41]Juris Hartmanis:
On the Succinctness of Different Representations of Languages. SIAM J. Comput. 9(1): 114-120 (1980) - [c22]Juris Hartmanis, Stephen R. Mahaney:
An Eassay about Research on Sparse NP Complete Sets. MFCS 1980: 40-57
1970 – 1979
- 1979
- [j40]Juris Hartmanis:
Relations Between Diagonalization, Proof Systems, and Complexity Gaps. Theor. Comput. Sci. 8: 239-253 (1979) - [c21]Juris Hartmanis:
Observations about the Development of Theoretical Computer Science. FOCS 1979: 224-233 - [c20]Theodore P. Baker, Juris Hartmanis:
Succinctness, Verifiability and Determinism in Representations of Polynomial-Time Languages. FOCS 1979: 392-396 - [c19]Juris Hartmanis:
On the Succintness of Different Representations of Languages. ICALP 1979: 282-288 - [c18]Juris Hartmanis, Theodore P. Baker:
Relative Succinctness of Representations of Languages and Separation of Complexity Classes. MFCS 1979: 70-88 - 1978
- [j39]Juris Hartmanis, Leonard Berman:
On Polynomial Time Isomorphisms of Some New Complete Sets. J. Comput. Syst. Sci. 16(3): 418-422 (1978) - [j38]Juris Hartmanis:
On Log-Tape Isomorphisms of Complete Sets. Theor. Comput. Sci. 7: 273-286 (1978) - [c17]Juris Hartmanis, Neil Immerman, Stephen R. Mahaney:
One-Way Log-Tape Reductions. FOCS 1978: 65-72 - 1977
- [j37]Leonard Berman, Juris Hartmanis:
On Isomorphisms and Density of NP and Other Complete Sets. SIAM J. Comput. 6(2): 305-322 (1977) - [c16]Juris Hartmanis:
Relations Between Diagonalization, Proof Systems, and Complexity Gaps (Preliminary Version). STOC 1977: 223-227 - [c15]Leonard Berman, Juris Hartmanis:
On polynomial time isomorphisms of complete sets. Theoretical Computer Science 1977: 1-16 - 1976
- [j36]Juris Hartmanis, Janos Simon:
On the Structure of Feasible Computations. Adv. Comput. 14: 1-43 (1976) - [j35]Juris Hartmanis:
On Effective Speed-Up and Long Proofs of Trivial Theorems in Formal Theories. RAIRO Theor. Informatics Appl. 10(1): 29-38 (1976) - [j34]Juris Hartmanis, John E. Hopcroft:
Independence results in computer science. SIGACT News 8(4): 13-24 (1976) - [j33]Juris Hartmanis, Leonard Berman:
On Tape Bounds for Single Letter Alphabet Language Processing. Theor. Comput. Sci. 3(2): 213-224 (1976) - [c14]Juris Hartmanis, Leonard Berman:
On Isomorphisms and Density of NP and Other Complete Sets. STOC 1976: 30-40 - 1975
- [j32]Juris Hartmanis:
Computational Complexity of Formal Translations. Math. Syst. Theory 8(2): 156-167 (1975) - [j31]Juris Hartmanis, Theodore P. Baker:
On Simple Gödel Numberings and Translations. SIAM J. Comput. 4(1): 1-11 (1975) - [c13]Juris Hartmanis, Leonard Berman:
A Note on Tape Bounds for SLA Language Processing. FOCS 1975: 65-70 - 1974
- [c12]Juris Hartmanis, Janos Simon:
On the Power of Multiplication in Random Access Machines. SWAT 1974: 13-23 - [c11]Juris Hartmanis, Janos Simon:
On the Structure of Feasible Computation. GI Jahrestagung 1974: 3-51 - [c10]Juris Hartmanis, Theodore P. Baker:
On Simple Goedel Numberings and Translations. ICALP 1974: 301-316 - 1973
- [j30]Juris Hartmanis, H. Walter:
Group Theoretic Characterization of Linear Permutation Automata. J. Comput. Syst. Sci. 7(2): 168-188 (1973) - [c9]Juris Hartmanis:
On the Problem of Finding Natural Computational Complexity Measures. MFCS 1973: 95-103 - 1972
- [j29]Juris Hartmanis:
On Non-Determinancy in Simple Computing Devices. Acta Informatica 1: 336-344 (1972) - 1971
- [j28]Juris Hartmanis, John E. Hopcroft:
An Overview of the Theory of Computational Complexity. J. ACM 18(2): 444-475 (1971) - [j27]Juris Hartmanis, Forbes D. Lewis:
The use of Lists in the Study of Undecidable Problems in Automata Theory. J. Comput. Syst. Sci. 5(1): 54-66 (1971) - [j26]Juris Hartmanis:
Computational Complexity of Random Acess Stored Program Machines. Math. Syst. Theory 5(3): 232-245 (1971) - [c8]Robert L. Constable, Juris Hartmanis:
Complexity of Formal Translations and Speed-Up Results. STOC 1971: 244-250 - 1970
- [j25]Juris Hartmanis, John E. Hopcroft:
What makes Some Language Theory Problems Undecidable. J. Comput. Syst. Sci. 4(4): 368-376 (1970) - [j24]Juris Hartmanis:
A Note on One-Way and Two-Way Automata. Math. Syst. Theory 4(1): 24-28 (1970) - [j23]George E. Forsythe, Bernard A. Galler, Juris Hartmanis, Alan J. Perlis, Joseph F. Traub:
Computer science and mathematics. ACM SIGCSE Bull. 2(4): 19-29 (1970) - [j22]Juris Hartmanis:
R70-1 A Note on Computing Time for the Recognition of Context- Free Languages by a Single-Tape Turing Machine. IEEE Trans. Computers 19(5): 463 (1970)
1960 – 1969
- 1969
- [j21]Juris Hartmanis, Richard Edwin Stearns:
Automata-based computational complexity. Inf. Sci. 1(2): 173-184 (1969) - [j20]Juris Hartmanis:
On the Complexity of Undecidable Problems in Automata Theory. J. ACM 16(1): 160-167 (1969) - [j19]Juris Hartmanis, H. Shank:
Two Memory Bounds for the Recognition of Primes by Automata. Math. Syst. Theory 3(2): 125-129 (1969) - 1968
- [j18]Juris Hartmanis:
Computational Complexity of One-Tape Turing Machine Computations. J. ACM 15(2): 325-339 (1968) - [j17]Juris Hartmanis, H. Shank:
On the Recognition of Primes by Automata. J. ACM 15(3): 382-389 (1968) - [j16]Juris Hartmanis:
Tape-Reversal Bounded Turing Machine Computations. J. Comput. Syst. Sci. 2(2): 117-135 (1968) - [c7]Juris Hartmanis, John E. Hopcroft:
Structure of Undecidable Problems in Automata Theory. SWAT 1968: 327-333 - [c6]Patrick C. Fischer, Juris Hartmanis, Manuel Blum:
Tape Reversal Complexity Hierarchies. SWAT 1968: 373-382 - 1967
- [j15]Juris Hartmanis:
On Memory Requirements for Context-Free Language Recognition. J. ACM 14(4): 663-665 (1967) - [j14]Juris Hartmanis, Wayne A. Davis:
Homomorphic Images of Linear Sequential Machines. J. Comput. Syst. Sci. 1(2): 155-165 (1967) - [c5]Juris Hartmanis:
On the Complexity of Undecidable Problems in Automata Theory. SWAT 1967: 112-116 - 1966
- [j13]Juris Hartmanis:
Minimal Feedback Realizations of Sequential Machines. IEEE Trans. Electron. Comput. 15(6): 931-933 (1966) - 1965
- [j12]Juris Hartmanis:
Two Tests for the Linearity of Sequential Machines. IEEE Trans. Electron. Comput. 14(6): 781-786 (1965) - [c4]Richard Edwin Stearns, Juris Hartmanis, Philip M. Lewis II:
Hierarchies of memory limited computations. SWCT 1965: 179-190 - [c3]Philip M. Lewis II, Richard Edwin Stearns, Juris Hartmanis:
Memory bounds for recognition of context-free and context-sensitive languages. SWCT 1965: 191-202 - 1964
- [j11]Juris Hartmanis, Richard Edwin Stearns:
Pair Algebra and Its Application to Automata Theory. Inf. Control. 7(4): 485-507 (1964) - [c2]Juris Hartmanis, Richard Edwin Stearns:
Computational complexity of recursive sequences. SWCT 1964: 82-90 - [c1]Richard Edwin Stearns, Juris Hartmanis:
On the application of pair algebra to automata theory. SWCT 1964: 192-196 - 1963
- [j10]Richard Edwin Stearns, Juris Hartmanis:
Regularity Preserving Modifications of Regular Expressions. Inf. Control. 6(1): 55-69 (1963) - [j9]Juris Hartmanis:
Further Results on the Structure of Sequential Machines. J. ACM 10(1): 78-88 (1963) - [j8]Juris Hartmanis, Richard Edwin Stearns:
A Study of Feedback and Errors in Sequential Machines. IEEE Trans. Electron. Comput. 12(3): 223-232 (1963) - 1962
- [j7]Juris Hartmanis:
Loop-Free Structure of Sequential Machines. Inf. Control. 5(1): 25-43 (1962) - [j6]Juris Hartmanis, Richard Edwin Stearns:
Some Dangers in State Reduction of Sequential Machines. Inf. Control. 5(3): 252-260 (1962) - [j5]Juris Hartmanis:
Maximal Autonomous Clocks of Sequential Machines. IRE Trans. Electron. Comput. 11(1): 83-86 (1962) - 1961
- [j4]Juris Hartmanis:
On the State Assignment Problem for Sequential Machines. I. IRE Trans. Electron. Comput. 10(2): 157-165 (1961) - [j3]Richard Edwin Stearns, Juris Hartmanis:
On the State Assignment Problem for Sequential Machines II. IRE Trans. Electron. Comput. 10(4): 593-603 (1961) - 1960
- [j2]Juris Hartmanis:
Symbolic Analysis of a Decomposition of Information Processing Machines. Inf. Control. 3(2): 154-178 (1960)
1950 – 1959
- 1959
- [j1]Juris Hartmanis:
The Applications of Some Basic Inequalities for Entropy. Inf. Control. 2(3): 199-213 (1959)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from , , and to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-24 22:54 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint