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) |