2003 |
110 | EE | Juris Hartmanis:
Separation of complexity classes.
J. ACM 50(1): 58-62 (2003) |
2001 |
109 | EE | Juris Hartmanis:
Computational Complexity and Mathematical Proofs.
Informatics 2001: 251-256 |
2000 |
108 | | Juris Hartmanis:
Undecidability and Incompleteness Results in Automata Theory.
A Half-Century of Automata Theory 2000: 21-35 |
1999 |
107 | EE | Juris Hartmanis:
Observations about the Nature and State of Computer Science (Keynote Address).
ICALP 1999: 105 |
1998 |
106 | | 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 |
105 | | Juris Hartmanis:
On the Computing Paradigm and Computational Complexity.
MFCS 1995: 82-92 |
104 | | Juris Hartmanis:
Response to the Essays "On Computational Complexity and the Nature of Computer Science".
ACM Comput. Surv. 27(1): 59-61 (1995) |
103 | | Juris Hartmanis:
Turing Award Lecture: On Computational Complexity and the Nature of Computer Science.
ACM Comput. Surv. 27(1): 7-16 (1995) |
102 | | Juris Hartmanis:
On the Weight of Computations.
Bulletin of the EATCS 55: (1995) |
1994 |
101 | | Juris Hartmanis,
Suresh Chari:
On the Intellectual Terrain Around NP.
CIAC 1994: 1-11 |
100 | | Juris Hartmanis:
The Structure of the Complexity of Computations: A Guided Tour Through Complexity Classes.
IFIP Congress (1) 1994: 213-220 |
99 | | Juris Hartmanis:
About the Nature of the Computer Science.
Bulletin of the EATCS 53: 170-190 (1994) |
98 | | Juris Hartmanis:
Turing Award Lecture: On Computational Complexity and the Nature of Computer Science.
Commun. ACM 37(10): 37-43 (1994) |
97 | | 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) |
96 | | 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 |
95 | EE | 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 |
94 | | Juris Hartmanis:
Some Observations About the Nature of Computer Science.
FSTTCS 1993: 1-12 |
93 | | Juris Hartmanis:
A Broader Research Agenda for Theory.
Bulletin of the EATCS 49: 125-129 (1993) |
1992 |
92 | | 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 |
91 | | Desh Ranjan,
Richard Chang,
Juris Hartmanis:
Space Bounded Computations: Review and New Separation Results.
Theor. Comput. Sci. 80(2): 289-302 (1991) |
90 | | Juris Hartmanis,
Lane A. Hemachandra:
One-Way Functions and the Nonisomorphism of NP-Complete Sets.
Theor. Comput. Sci. 81(1): 155-163 (1991) |
1990 |
89 | | Juris Hartmanis,
Richard Chang,
Desh Ranjan,
Pankaj Rohatgi:
Structural Complexity Theory: recent Surprises.
SWAT 1990: 1-12 |
88 | | Juris Hartmanis,
Richard Chang,
Desh Ranjan,
Pankaj Rohatgi:
On Unique Staisfiability and Randomized Reductions.
Bulletin of the EATCS 41: 166-174 (1990) |
87 | | Juris Hartmanis:
New Developments in Structural Complexity Theory.
Theor. Comput. Sci. 71(1): 79-93 (1990) |
86 | | Juris Hartmanis,
Lane A. Hemachandra:
Robust Machines Accept Easy Sets.
Theor. Comput. Sci. 74(2): 217-225 (1990) |
1989 |
85 | | Juris Hartmanis,
Desh Ranjan:
Space Bounded Computations: Review And New Separation Results.
MFCS 1989: 49-66 |
84 | | Jin-yi Cai,
Juris Hartmanis:
The Complexity Of The Real Line Is A Fractal.
Structure in Complexity Theory Conference 1989: 138-146 |
83 | | Juris Hartmanis:
The Structural Complexity Column.
Bulletin of the EATCS 37: 117-126 (1989) |
82 | | Juris Hartmanis:
The Structural Complexity Column.
Bulletin of the EATCS 38: 101-106 (1989) |
81 | | 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) |
80 | | 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 |
79 | | Juris Hartmanis:
New Developments in Structural Complexity Theory.
ICALP 1988: 271-286 |
78 | | Juris Hartmanis:
The Structural Complexity Column.
Bulletin of the EATCS 35: 82-91 (1988) |
77 | | Juris Hartmanis,
Lane A. Hemachandra:
On Sparse Oracles Separating Feasible Complexity Classes.
Inf. Process. Lett. 28(6): 291-295 (1988) |
76 | | 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) |
75 | | Juris Hartmanis,
Lane A. Hemachandra:
Complexity Classes without Machines: On Complete Languages for UP.
Theor. Comput. Sci. 58: 129-142 (1988) |
1987 |
74 | | Juris Hartmanis:
Some Observations of NP Complete Sets.
FCT 1987: 185-196 |
73 | | 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) |
72 | | Juris Hartmanis:
The Structural Complexity Column.
Bulletin of the EATCS 33: 26-39 (1987) |
1986 |
71 | | Juris Hartmanis,
Lane A. Hemachandra:
Complexity Classes Without Machines: On Complete Languages for UP.
ICALP 1986: 123-135 |
70 | | Juris Hartmanis,
Ming Li,
Yaacov Yesha:
Containment, Separation, Complete Sets, and Immunity of Complexity Classes.
ICALP 1986: 136-145 |
69 | | Juris Hartmanis:
Pragmatic Aspects of Complexity Theory (Panel).
IFIP Congress 1986: 3-4 |
68 | | Juris Hartmanis,
Lane A. Hemachandra:
On Sparse Oracles Separating Feasible Complexity Classes.
STACS 1986: 321-333 |
1985 |
67 | | Juris Hartmanis,
Neil Immerman:
On Complete Problems for NP$\cap$CoNP.
ICALP 1985: 250-259 |
66 | | Juris Hartmanis:
Solvable problems with conflicting relativizations.
Bulletin of the EATCS 27: 40-48 (1985) |
65 | | Juris Hartmanis:
Independence Results About Context-Free Languages and Lower Bounds.
Inf. Process. Lett. 20(5): 241-248 (1985) |
64 | | Juris Hartmanis,
Neil Immerman,
Vivian Sewelson:
Sparse Sets in NP-P: EXPTIME versus NEXPTIME
Information and Control 65(2/3): 158-181 (1985) |
1984 |
63 | | Juris Hartmanis:
On non-isomorphic NP complete sets.
Bulletin of the EATCS 24: 73-77 (1984) |
62 | | Juris Hartmanis,
Yaacov Yesha:
Computation Times of NP Sets of Different Densities.
Theor. Comput. Sci. 34: 17-32 (1984) |
1983 |
61 | | Juris Hartmanis:
Generalized Kolmogorov Complexity and the Structure of Feasible Computations (Preliminary Report)
FOCS 1983: 439-445 |
60 | | Juris Hartmanis,
Juris Hartmanis,
Yaacov Yesha:
Computation Times of NP Sets of Different Densities.
ICALP 1983: 319-330 |
59 | | Juris Hartmanis,
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 | EE | 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 | EE | 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 | EE | Juris Hartmanis:
Computational Complexity of One-Tape Turing Machine Computations.
J. ACM 15(2): 325-339 (1968) |
16 | EE | 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 | EE | 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 | EE | 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) |