 | 2003 |
|---|
| 109 |       | Juris Hartmanis:
Separation of complexity classes.
J. ACM 50(1): 58-62 (2003) |
| 2001 |
|---|
| 108 | | Juris Hartmanis:
Computational Complexity and Mathematical Proofs.
Informatics 2001: 251-256 |
| 2000 |
|---|
| 107 |  | Juris Hartmanis:
Undecidability and Incompleteness Results in Automata Theory.
A Half-Century of Automata Theory 2000: 21-35 |
| 1999 |
|---|
| 106 | | Juris Hartmanis:
Observations about the Nature and State of Computer Science (Keynote Address).
ICALP 1999: 105 |
| 1998 |
|---|
| 105 | | 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.
IEEE Computer 31: 29-38 (1998) |
| 1995 |
|---|
| 104 | | Juris Hartmanis:
On the Computing Paradigm and Computational Complexity.
MFCS 1995: 82-92 |
| 103 | | Juris Hartmanis:
Response to the Essays "On Computational Complexity and the Nature of Computer Science".
ACM Comput. Surv. 27(1): 59-61 (1995) |
| 102 | | Juris Hartmanis:
Turing Award Lecture: On Computational Complexity and the Nature of Computer Science.
ACM Comput. Surv. 27(1): 7-16 (1995) |
| 101 | | Juris Hartmanis:
On the Weight of Computations.
Bulletin of the EATCS 55: (1995) |
| 1994 |
|---|
| 100 | | Juris Hartmanis,
Suresh Chari:
On the Intellectual Terrain Around NP.
CIAC 1994: 1-11 |
| 99 | | Juris Hartmanis:
The Structure of the Complexity of Computations: A Guided Tour Through Complexity Classes.
IFIP Congress (1) 1994: 213-220 |
| 98 | | Juris Hartmanis:
About the Nature of the Computer Science.
Bulletin of the EATCS 53: 170-190 (1994) |
| 97 | | Juris Hartmanis:
Turing Award Lecture: On Computational Complexity and the Nature of Computer Science.
Commun. ACM 37(10): 37-43 (1994) |
| 96 | | 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) |
| 95 | | 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) |
| 1993 |
|---|
| 94 | | 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 |
| 93 | | Juris Hartmanis:
Some Observations About the Nature of Computer Science.
FSTTCS 1993: 1-12 |
| 92 | | Juris Hartmanis:
A Broader Research Agenda for Theory.
Bulletin of the EATCS 49: 125-129 (1993) |
| 1992 |
|---|
| 91 | | 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 |
|---|
| 90 | | Desh Ranjan,
Richard Chang,
Juris Hartmanis:
Space Bounded Computations: Review and New Separation Results.
Theor. Comput. Sci. 80(2): 289-302 (1991) |
| 89 | | Juris Hartmanis,
Lane A. Hemachandra:
One-Way Functions and the Nonisomorphism of NP-Complete Sets.
Theor. Comput. Sci. 81(1): 155-163 (1991) |
| 1990 |
|---|
| 88 | | Juris Hartmanis,
Richard Chang,
Desh Ranjan,
Pankaj Rohatgi:
Structural Complexity Theory: recent Surprises.
SWAT 1990: 1-12 |
| 87 | | Juris Hartmanis,
Richard Chang,
Desh Ranjan,
Pankaj Rohatgi:
On Unique Staisfiability and Randomized Reductions.
Bulletin of the EATCS 41: 166-174 (1990) |
| 86 | | Juris Hartmanis:
New Developments in Structural Complexity Theory.
Theor. Comput. Sci. 71(1): 79-93 (1990) |
| 85 | | Juris Hartmanis,
Lane A. Hemachandra:
Robust Machines Accept Easy Sets.
Theor. Comput. Sci. 74(2): 217-225 (1990) |
| 1989 |
|---|
| 84 | | Juris Hartmanis,
Desh Ranjan:
Space Bounded Computations: Review And New Separation Results.
MFCS 1989: 49-66 |
| 83 | | Jin-yi Cai,
Juris Hartmanis:
The Complexity Of The Real Line Is A Fractal.
Structure in Complexity Theory Conference 1989: 138-146 |
| 82 | | Juris Hartmanis:
The Structural Complexity Column.
Bulletin of the EATCS 37: 117-126 (1989) |
| 81 | | Juris Hartmanis:
The Structural Complexity Column.
Bulletin of the EATCS 38: 101-106 (1989) |
| 80 | | 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) |
| 79 | | 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) |
| 1988 |
|---|
| 78 | | Juris Hartmanis:
New Developments in Structural Complexity Theory.
ICALP 1988: 271-286 |
| 77 | | Juris Hartmanis:
The Structural Complexity Column.
Bulletin of the EATCS 35: 82-91 (1988) |
| 76 | | Juris Hartmanis,
Lane A. Hemachandra:
On Sparse Oracles Separating Feasible Complexity Classes.
Inf. Process. Lett. 28(6): 291-295 (1988) |
| 75 | | 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) |
| 74 | | Juris Hartmanis,
Lane A. Hemachandra:
Complexity Classes without Machines: On Complete Languages for UP.
Theor. Comput. Sci. 58: 129-142 (1988) |
| 1987 |
|---|
| 73 | | Juris Hartmanis:
Some Observations of NP Complete Sets.
FCT 1987: 185-196 |
| 72 | | Juris Hartmanis:
Structural Complexity Columns in Sparse complete sets for NP and the optimal collpase of the polynomial hierarchy.
Bulletin of the EATCS 32: 73-81 (1987) |
| 71 | | Juris Hartmanis:
The Structural Complexity Column.
Bulletin of the EATCS 33: 26-39 (1987) |
| 1986 |
|---|
| 70 | | Juris Hartmanis,
Lane A. Hemachandra:
Complexity Classes Without Machines: On Complete Languages for UP.
ICALP 1986: 123-135 |
| 69 | | Juris Hartmanis,
Ming Li,
Yaacov Yesha:
Containment, Separation, Complete Sets, and Immunity of Complexity Classes.
ICALP 1986: 136-145 |
| 68 | | Juris Hartmanis:
Pragmatic Aspects of Complexity Theory (Panel).
IFIP Congress 1986: 3-4 |
| 67 | | Juris Hartmanis,
Lane A. Hemachandra:
On Sparse Oracles Separating Feasible Complexity Classes.
STACS 1986: 321-333 |
| 1985 |
|---|
| 66 | | Juris Hartmanis,
Neil Immerman:
On Complete Problems for NP$\cap$CoNP.
ICALP 1985: 250-259 |
| 65 | | Juris Hartmanis:
Solvable problems with conflicting relativizations.
Bulletin of the EATCS 27: 40-48 (1985) |
| 64 | | Juris Hartmanis:
Independence Results About Context-Free Languages and Lower Bounds.
Inf. Process. Lett. 20(5): 241-248 (1985) |
| 63 | | Juris Hartmanis,
Neil Immerman,
Vivian Sewelson:
Sparse Sets in NP-P: EXPTIME versus NEXPTIME
Information and Control 65(2/3): 158-181 (1985) |
| 1984 |
|---|
| 62 | | Juris Hartmanis:
On non-isomorphic NP complete sets.
Bulletin of the EATCS 24: 73-77 (1984) |
| 61 | | Juris Hartmanis,
Yaacov Yesha:
Computation Times of NP Sets of Different Densities.
Theor. Comput. Sci. 34: 17-32 (1984) |
| 1983 |
|---|
| 60 | | Juris Hartmanis:
Generalized Kolmogorov Complexity and the Structure of Feasible Computations (Preliminary Report)
FOCS 1983: 439-445 |
| 59 | | Juris Hartmanis,
Yaacov Yesha:
Computation Times of NP Sets of Different Densities.
ICALP 1983: 319-330 |
| 58 | | Juris Hartmanis,
Vivian Sewelson,
Neil Immerman:
Sparse Sets in NP-P: EXPTIME versus NEXPTIME
STOC 1983: 382-391 |
| 57 | | Juris Hartmanis:
On Sparse Sets in NP - P.
Inf. Process. Lett. 16(2): 55-60 (1983) |
| 56 | | Juris Hartmanis:
On Gödel Speed-Up and Succinctness of Language Representations.
Theor. Comput. Sci. 26: 335-342 (1983) |
| 1982 |
|---|
| 55 | | Juris Hartmanis:
A Note on Natural Complete Sets and Gödel Numberings.
Theor. Comput. Sci. 17: 75-89 (1982) |
| 1981 |
|---|
| 54 | | 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 |
|---|
| 53 | | Juris Hartmanis,
Stephen R. Mahaney:
An Eassay about Research on Sparse NP Complete Sets.
MFCS 1980: 40-57 |
| 52 | | Juris Hartmanis:
On the Succinctness of Different Representations of Languages.
SIAM J. Comput. 9(1): 114-120 (1980) |
| 1979 |
|---|
| 51 | | Juris Hartmanis:
Observations about the Development of Theoretical Computer Science
FOCS 1979: 224-233 |
| 50 | | Theodore P. Baker,
Juris Hartmanis:
Succinctness, Verifiability and Determinism in Representations of Polynomial-Time Languages
FOCS 1979: 392-396 |
| 49 | | Juris Hartmanis:
On the Succintness of Different Representations of Languages.
ICALP 1979: 282-288 |
| 48 | | Juris Hartmanis,
Theodore P. Baker:
Relative Succinctness of Representations of Languages and Separation of Complexity Classes.
MFCS 1979: 70-88 |
| 47 | | Juris Hartmanis:
Relations Between Diagonalization, Proof Systems, and Complexity Gaps.
Theor. Comput. Sci. 8: 239-253 (1979) |
| 1978 |
|---|
| 46 | | Juris Hartmanis,
Neil Immerman,
Stephen R. Mahaney:
One-Way Log-Tape Reductions
FOCS 1978: 65-72 |
| 45 | | Juris Hartmanis,
Leonard Berman:
On Polynomial Time Isomorphisms of Some New Complete Sets.
J. Comput. Syst. Sci. 16(3): 418-422 (1978) |
| 44 | | Juris Hartmanis:
On Log-Tape Isomorphisms of Complete Sets.
Theor. Comput. Sci. 7: 273-286 (1978) |
| 1977 |
|---|
| 43 | | Juris Hartmanis:
Relations Between Diagonalization, Proof Systems, and Complexity Gaps (Preliminary Version)
STOC 1977: 223-227 |
| 42 | | Leonard Berman,
Juris Hartmanis:
On polynomial time isomorphisms of complete sets.
Theoretical Computer Science 1977: 1-16 |
| 41 | | Leonard Berman,
Juris Hartmanis:
On Isomorphisms and Density of NP and Other Complete Sets.
SIAM J. Comput. 6(2): 305-322 (1977) |
| 1976 |
|---|
| 40 | | Juris Hartmanis,
Leonard Berman:
On Isomorphisms and Density of NP and Other Complete Sets
STOC 1976: 30-40 |
| 39 | | Juris Hartmanis,
Janos Simon:
On the Structure of Feasible Computations.
Advances in Computers 14: 1-43 (1976) |
| 38 | | Juris Hartmanis:
On Effective Speed-Up and Long Proofs of Trivial Theorems in Formal Theories.
ITA 10(1): 29-38 (1976) |
| 37 | | Juris Hartmanis,
Leonard Berman:
On Tape Bounds for Single Letter Alphabet Language Processing.
Theor. Comput. Sci. 3(2): 213-224 (1976) |
| 1975 |
|---|
| 36 | | Juris Hartmanis,
Leonard Berman:
A Note on Tape Bounds for SLA Language Processing
FOCS 1975: 65-70 |
| 35 | | Juris Hartmanis:
Computational Complexity of Formal Translations.
Mathematical Systems Theory 8(2): 156-167 (1975) |
| 34 | | Juris Hartmanis,
Theodore P. Baker:
On Simple Gödel Numberings and Translations.
SIAM J. Comput. 4(1): 1-11 (1975) |
| 1974 |
|---|
| 33 | | Juris Hartmanis,
Janos Simon:
On the Power of Multiplication in Random Access Machines
FOCS 1974: 13-23 |
| 32 | | Juris Hartmanis,
Janos Simon:
On the Structure of Feasible Computation.
GI Jahrestagung 1974: 3-51 |
| 31 | | Juris Hartmanis,
Theodore P. Baker:
On Simple Goedel Numberings and Translations.
ICALP 1974: 301-316 |
| 1973 |
|---|
| 30 | | Juris Hartmanis:
On the Problem of Finding Natural Computational Complexity Measures.
MFCS 1973: 95-103 |
| 29 | | Juris Hartmanis,
H. Walter:
Group Theoretic Characterization of Linear Permutation Automata.
J. Comput. Syst. Sci. 7(2): 168-188 (1973) |
| 1972 |
|---|
| 28 | | Juris Hartmanis:
On Non-Determinancy in Simple Computing Devices
Acta Inf. 1: 336-344 (1972) |
| 1971 |
|---|
| 27 | | Robert L. Constable,
Juris Hartmanis:
Complexity of Formal Translations and Speed-Up Results
STOC 1971: 244-250 |
| 26 | | Juris Hartmanis,
John E. Hopcroft:
An Overview of the Theory of Computational Complexity.
J. ACM 18(2): 444-475 (1971) |
| 25 | | 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) |
| 24 | | Juris Hartmanis:
Computational Complexity of Random Acess Stored Program Machines.
Mathematical Systems Theory 5(3): 232-245 (1971) |
| 1970 |
|---|
| 23 | | Juris Hartmanis,
John E. Hopcroft:
What makes Some Language Theory Problems Undecidable.
J. Comput. Syst. Sci. 4(4): 368-376 (1970) |
| 22 | | Juris Hartmanis:
A Note on One-Way and Two-Way Automata.
Mathematical Systems Theory 4(1): 24-28 (1970) |
| 1969 |
|---|
| 21 | | Juris Hartmanis:
On the Complexity of Undecidable Problems in Automata Theory.
J. ACM 16(1): 160-167 (1969) |
| 20 | | Juris Hartmanis,
H. Shank:
Two Memory Bounds for the Recognition of Primes by Automata.
Mathematical Systems Theory 3(2): 125-129 (1969) |
| 1968 |
|---|
| 19 | | Juris Hartmanis,
John E. Hopcroft:
Structure of Undecidable Problems in Automata Theory
FOCS 1968: 327-333 |
| 18 | | Patrick C. Fischer,
Juris Hartmanis,
Manuel Blum:
Tape Reversal Complexity Hierarchies
FOCS 1968: 373-382 |
| 17 | | Juris Hartmanis:
Computational Complexity of One-Tape Turing Machine Computations.
J. ACM 15(2): 325-339 (1968) |
| 16 | | Juris Hartmanis,
H. Shank:
On the Recognition of Primes by Automata.
J. ACM 15(3): 382-389 (1968) |
| 15 | | Juris Hartmanis:
Tape-Reversal Bounded Turing Machine Computations.
J. Comput. Syst. Sci. 2(2): 117-135 (1968) |
| 1967 |
|---|
| 14 | | Juris Hartmanis:
On the Complexity of Undecidable Problems in Automata Theory
FOCS 1967: 112-116 |
| 13 | | Juris Hartmanis:
On Memory Requirements for Context-Free Language Recognition.
J. ACM 14(4): 663-665 (1967) |
| 12 | | Juris Hartmanis,
Wayne A. Davis:
Homomorphic Images of Linear Sequential Machines.
J. Comput. Syst. Sci. 1(2): 155-165 (1967) |
| 1965 |
|---|
| 11 | | Richard Edwin Stearns,
Juris Hartmanis,
Philip M. Lewis II:
Hierarchies of memory limited computations
FOCS 1965: 179-190 |
| 10 | | Philip M. Lewis II,
Richard Edwin Stearns,
Juris Hartmanis:
Memory bounds for recognition of context-free and context-sensitive languages
FOCS 1965: 191-202 |
| 1964 |
|---|
| 9 | | Richard Edwin Stearns,
Juris Hartmanis:
On the application of pair algebra to automata theory
FOCS 1964: 192-196 |
| 8 | | Juris Hartmanis,
Richard Edwin Stearns:
Computational complexity of recursive sequences
FOCS 1964: 82-90 |
| 7 | | Juris Hartmanis,
Richard Edwin Stearns:
Pair Algebra and Its Application to Automata Theory
Information and Control 7(4): 485-507 (1964) |
| 1963 |
|---|
| 6 | | Richard Edwin Stearns,
Juris Hartmanis:
Regularity Preserving Modifications of Regular Expressions
Information and Control 6(1): 55-69 (1963) |
| 5 | | Juris Hartmanis:
Further Results on the Structure of Sequential Machines.
J. ACM 10(1): 78-88 (1963) |
| 1962 |
|---|
| 4 | | Juris Hartmanis:
Loop-Free Structure of Sequential Machines
Information and Control 5(1): 25-43 (1962) |
| 3 | | Juris Hartmanis,
Richard Edwin Stearns:
Some Dangers in State Reduction of Sequential Machines
Information and Control 5(3): 252-260 (1962) |
| 1960 |
|---|
| 2 | | Juris Hartmanis:
Symbolic Analysis of a Decomposition of Information Processing Machines
Information and Control 3(2): 154-178 (1960) |
| 1959 |
|---|
| 1 | | Juris Hartmanis:
The Applications of Some Basic Inequalities for Entropy
Information and Control 2(3): 199-213 (1959) |
