☰

Juris Hartmanis - Publications

Affiliations: 
Cornell University, Ithaca, NY, United States 
Tree Info Similar researchers PubMed Report error

55 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2001 Hartmanis J. Computational Complexity and Mathematical Proofs Lecture Notes in Computer Science. 251-256. DOI: 10.1007/3-540-44577-3_17  0.39
1995 Hartmanis J. Response to the essay “On computational complexity and the nature of computer science” Acm Computing Surveys. 27: 59-61. DOI: 10.1145/214037.214097  0.318
1995 Hartmanis J. On computational complexity and the nature of computer science Acm Computing Surveys. 27: 7-16. DOI: 10.1145/214037.214040  0.324
1994 Hartmanis J. Turing Award lecture on computational complexity and the nature of computer science Communications of the Acm. 37: 37-43. DOI: 10.1145/194313.214781  0.328
1994 Chang R, Chor B, Goldreich O, Hartmanis J, Håstad J, Ranjan D, Rohatgi P. The random oracle hypothesis is false Journal of Computer and System Sciences. 49: 24-39. DOI: 10.1016/S0022-0000(05)80084-4  0.32
1991 Hartmanis J, Hemachandra LA. One-way functions and the nonisomorphism of NP-complete sets Theoretical Computer Science. 81: 155-163. DOI: 10.1016/0304-3975(91)90323-T  0.332
1990 Hartmanis J, Hemachandra LA. Robust machines accept easy sets Theoretical Computer Science. 74: 217-225. DOI: 10.1016/0304-3975(90)90138-8  0.423
1988 Cai J, Gundermann T, Hartmanis J, Hemachandra LA, Sewelson V, Wagner K, Wechsung G. The Boolean hierarchy I: structural properties Siam Journal On Computing. 17: 1232-1252. DOI: 10.1137/0217078  0.383
1988 Hartmanis J, Hemachandra LA. Complexity classes without machines: on complete languages for UP Theoretical Computer Science. 58: 129-142. DOI: 10.1016/0304-3975(88)90022-9  0.407
1988 Hartmanis J, Hemachandra L. On sparse oracles separating feasible complexity classes Information Processing Letters. 28: 291-295. DOI: 10.1016/0020-0190(88)90176-7  0.365
1985 Hartmanis J, Immerman N, Sewelson V. Sparse sets in NP-P: EXPTIME versus NEXPTIME Information and Control. 65: 158-181. DOI: 10.1016/S0019-9958(85)80004-8  0.371
1985 Hartmanis J. Independence Results about Context-Free Languages and Lower Bounds Information Processing Letters. 20: 241-248. DOI: 10.1016/0020-0190(85)90026-2  0.355
1984 Hartmanis J, Yesha Y. Computation times of NP sets of different densities Theoretical Computer Science. 34: 17-32. DOI: 10.1016/0304-3975(84)90111-7  0.403
1983 Hartmanis J. On Gödel speed-up and succinctness of language representations Theoretical Computer Science. 26: 335-342. DOI: 10.1016/0304-3975(83)90016-6  0.337
1982 Hartmanis J. A note on natural complete sets and Gödel numberings Theoretical Computer Science. 17: 75-89. DOI: 10.1016/0304-3975(82)90132-3  0.345
1982 Hartmanis J. On Sparse Sets in NP-P Information Processing Letters. 16: 55-60. DOI: 10.1016/0020-0190(83)90024-8  0.338
1981 Hartmanis J, Mahaney SR. Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata Siam Journal On Computing. 10: 383-390. DOI: 10.1137/0210027  0.301
1980 Hartmanis J. On the Succinctness of Different Representations of Languages Siam Journal On Computing. 9: 114-120. DOI: 10.1137/0209010  0.335
1979 Hartmanis J. Relations between diagonalization, proof systems, and complexity gaps☆ Theoretical Computer Science. 8: 239-253. DOI: 10.1016/0304-3975(79)90047-1  0.439
1978 Hartmanis J. On log-tape isomorphisms of complete sets☆ Theoretical Computer Science. 7: 273-286. DOI: 10.1016/0304-3975(78)90018-X  0.377
1978 Hartmanis J, Berman L. On polynomial time isomorphisms of some new complete sets Journal of Computer and System Sciences. 16: 418-422. DOI: 10.1016/0022-0000(78)90027-2  0.399
1977 Berman L, Hartmanis J. On Isomorphisms and Density of $NP$ and Other Complete Sets Siam Journal On Computing. 6: 305-322. DOI: 10.1137/0206023  0.368
1977 Berman L, Hartmanis J. On polynomial time isomorphisms of complete sets Theoretical Computer Science. 1-16. DOI: 10.1007/3-540-08138-0_1  0.332
1976 Hartmanis J, Hopcroft JE. Independence results in computer science Acm Sigact News. 8: 13-24. DOI: 10.1145/1008335.1008336  0.355
1976 Hartmanis J, Berman L. On tape bounds for single letter alphabet language processing Theoretical Computer Science. 3: 213-224. DOI: 10.1016/0304-3975(76)90024-4  0.348
1975 Hartmanis J, Baker TP. On Simple Goedel Numberings and Translations Siam Journal On Computing. 4: 1-11. DOI: 10.1137/0204001  0.316
1974 Hartmanis J. Computational Complexity of Formal Translations Theory of Computing Systems \/ Mathematical Systems Theory. 8: 156-166. DOI: 10.1007/Bf01762186  0.376
1974 Hartmanis J, Simon J. On the Structure of Feasible Computation Advances in Computers. 14: 3-51. DOI: 10.1007/978-3-662-40087-6_1  0.369
1972 Hartmanis J. On non-determinancy in simple computing devices Acta Informatica. 1: 336-344. DOI: 10.1007/Bf00289513  0.415
1971 Hartmanis J, Hopcroft JE. An Overview of the Theory of Computational Complexity Journal of the Acm (Jacm). 18: 444-475. DOI: 10.1145/321650.321661  0.367
1971 Hartmanis J, Lewis FD. The use of lists in the study of undecidable problemsin automata theory Journal of Computer and System Sciences. 5: 54-66. DOI: 10.1016/S0022-0000(71)80007-7  0.358
1970 Hartmanis J, Hopcroft JE. What makes some language theory problems undecidable Journal of Computer and System Sciences. 4: 368-376. DOI: 10.1016/S0022-0000(70)80018-6  0.354
1970 Hartmanis J. Computational Complexity of Random Access Stored Program Machines Theory of Computing Systems \/ Mathematical Systems Theory. 5: 232-245. DOI: 10.1007/Bf01694180  0.368
1969 Hartmanis J. On the Complexity of Undecidable Problems in Automata Theory Journal of the Acm. 16: 160-167. DOI: 10.1145/321495.321507  0.399
1969 Hartmanis J, Stearns RE. Automata-based computational complexity Information Sciences. 1: 173-184. DOI: 10.1016/0020-0255(69)90014-0  0.397
1969 Hartmanis J. A Note on One-way and Two-way Automata Theory of Computing Systems \/ Mathematical Systems Theory. 4: 24-28. DOI: 10.1007/Bf01705881  0.316
1968 Hartmanis J, Shank H. On the Recognition of Primes by Automata Journal of the Acm. 15: 382-389. DOI: 10.1145/321466.321470  0.366
1968 Hartmanis J. Computational Complexity of One-Tape Turing Machine Computations Journal of the Acm. 15: 325-339. DOI: 10.1145/321450.321464  0.46
1968 Hartmanis J. Tape-reversal bounded turing machine computations Journal of Computer and System Sciences. 2: 117-135. DOI: 10.1016/S0022-0000(68)80027-3  0.43
1967 Hartmanis J. Sets of Numbers Defined by Finite Automata American Mathematical Monthly. 74: 539. DOI: 10.2307/2314883  0.313
1967 Hartmanis J. On Memory Requirements for Context-Free Language Recognition Journal of the Acm. 14: 663-665. DOI: 10.1145/321420.321424  0.344
1967 Hartmanis J, Davis WA. Homomorphic images of linear sequential machines Journal of Computer and System Sciences. 1: 155-165. DOI: 10.1016/S0022-0000(67)80012-6  0.325
1966 Hartmanis J. Minimal Feedback Realizations of Sequential Machines Ieee Transactions On Electronic Computers. 15: 931-933. DOI: 10.1109/Pgec.1966.264479  0.304
1965 Hartmanis J. Two Tests for the Linearity of Sequential Machines Ieee Transactions On Electronic Computers. 14: 781-786. DOI: 10.1109/Pgec.1965.264048  0.345
1964 Hartmanis J, Stearns RE. Pair algebra and its application to automata theory Information and Control. 7: 485-507. DOI: 10.1016/S0019-9958(64)90181-0  0.308
1963 Hartmanis J. Further Results on the Structure of Sequential Machines Journal of the Acm. 10: 78-88. DOI: 10.1145/321150.321155  0.307
1963 Hartmanis J, Stearns RE. A Study of Feedback and Errors in Sequential Machines Ieee Transactions On Electronic Computers. 223-232. DOI: 10.1109/Pgec.1963.263532  0.339
1963 Hartmanis J. The Equivalence of Sequential Machine Models Ieee Transactions On Electronic Computers. 1: 18-19. DOI: 10.1109/Pgec.1963.263389  0.309
1963 Stearns RE, Hartmanis J. Regularity preserving modifications of regular expressions Information and Control. 6: 55-69. DOI: 10.1016/S0019-9958(63)90110-4  0.304
1962 Hartmanis J. Maximal Autonomous Clocks of Sequential Machines Ire Transactions On Electronic Computers. 11: 83-86. DOI: 10.1109/Tec.1962.5219325  0.334
1962 Hartmanis J, Stearns RE. Some dangers in state reduction of sequential machines Information and Control. 5: 252-260. DOI: 10.1016/S0019-9958(62)90588-0  0.331
1962 Hartmanis J. Loop-free structure of sequential machines Information & Computation. 5: 25-43. DOI: 10.1016/S0019-9958(62)90193-6  0.371
1961 Stearns RE, Hartmanis J. On the State Assignment Problem for Sequential Machines II Ire Transactions On Electronic Computers. 593-603. DOI: 10.1109/Tec.1961.5219184  0.369
1960 Hartmanis J. Symbolic Analysis of a Decomposition of Information Processing Machines Information & Computation. 3: 154-178. DOI: 10.1016/S0019-9958(60)90744-0  0.388
1959 Hartmanis J. Lattice Theory of Generalized Partitions Canadian Journal of Mathematics. 11: 97-106. DOI: 10.4153/Cjm-1959-013-8  0.303
Show low-probability matches.