Publications: Technical Articles, Theses, and Reports

  1. Two applications of hand-printed two-dimensional computer input; A.B. Thesis, Harvard University, Cambridge, Massachusetts, 1968
  2. SHAPESHIFTER: An interactive program for experimenting with com\-plex-plane transformations; Proceedings of the 23rd National Conference of the Association for Computing Machinery, 1968; pp. 717--724
  3. An interactive graphics facility under the PDP-10/50 timesharing monitor; Proceedings of the DECUS Fall 1969 Conference; pp. 59--62
  4. Techniques for generating, manipulating, and storage management of type 340 display files; Proceedings of the DECUS Fall 1969 Conference; pp. 67--74
  5. (with Malcolm C. Bruce) A device to make a Rand tablet act like a light pen; Proceedings of the DECUS Spring 1970 Conference; pp. 249--251
  6. (with Warren D. Goldfarb) The decision problem for formulas with a small number of atomic subformulas; Journal of Symbolic Logic, 38 (1973); pp.471--480
  7. Stal O. Aanderaa and Harry R. Lewis, Prefix classes of Krom formulas; Journal of Symbolic Logic, 38 (1973); pp. 628--642
  8. Herbrand Expansions and Reductions of the Decision Problem; Ph.D. Thesis, Division of Engineering and Applied Physics, Harvard University, 1974
  9. Stal O. Aanderaa and Harry R. Lewis, Linear sampling and the AEA case of the decision problem; Journal of Symbolic Logic, 39 (1974); pp. 519--548
  10. Program schemata and the first-order decision problem; Journal of Computer and Systems Sciences, 8 (1974); pp. 71--83
  11. Description of restricted automata by first-order formulae; Mathematical Systems Theory, 9 (1975); pp. 97--104
  12. Warren D. Goldfarb and Harry R. Lewis, Skolem reduction classes; Journal of Symbolic Logic, 40 (1975); pp. 62--68
  13. Krom formulas with one dyadic predicate letter; Journal of Symbolic Logic, 41 (1976); pp. 341--362
  14. Renaming a set of clauses as a Horn set; Journal of the Association for Computing Machinery, 10 (1978); pp. 134--135
  15. The equivalence problem for program schemata with nonintersecting loops; Proceedings of the Fourth Association for Computing Machinery Symposium on Principles of Programming Languages, 1977; pp. 253--266
  16. Harry R. Lewis and John H. Reif, Symbolic evaluation and the global value graph; Proceedings of the Fourth Association for Computing Machinery Symposium on Principles of Programming Languages, 1977; pp. 102--118
  17. Complexity measures for combinatorial decision problems of the tiling variety; Proceedings of the Conference on Theoretical Computer Science held at Waterloo, Ontario, August, 1977; pp. 62--73
  18. A new decidable problem, with applications; Proceedings of the 18th Symposium on Foundations of Computer Science, 1977; pp.~62--73
  19. Harry R. Lewis and Christos H. Papadimitriou, Efficient computability; Scientific American, 238 (1978); pp. 253--266
  20. Henry H. Leitner and Harry R. Lewis, Why Johnny can't program; Proceedings of the SIGCSE/CSA Technical Symposium on Computer Science Education, SIGCSE Bulletin, 10, 1 (1978); pp. 266--276
  21. William R. Franklin and Harry R. Lewis, 3-D display of discrete spatial data by prism maps; Computer Graphics, 12 (1978); pp. 70--75
  22. Complexity of solvable cases of the decision problem for the predicate calculus; Proceedings of the Nineteenth IEEE Symposium on the Foundations of Computer Science, 1978; pp. 35--47
  23. Review of Mariages Stables by Donald E. Knuth; SIGACT NEWS; Winter 1978
  24. Satisfiability problems for propositional calculi; Mathematical Systems Theory, 13 (1979); pp. 45--54
  25. Complexity results for classes of quantificational formulas; Journal of Computer and Systems Sciences, 21 (1980); pp. 317--353
  26. Stal O. Aanderaa, Egon Borger, and Harry R. Lewis, Conservative reduction classes of Krom formulas; Journal of Symbolic Logic, 19 (1982); pp. 110-130
  27. Harry R. Lewis and Christos H. Papadimitriou, Symmetric space-bounded computation, extended abstract; Proceedings of the 7th International Colloquium on Automata, Languages, and Programming; Springer-Verlag Lecture Notes in Computer Science, 85, pp. 374--384
  28. Harry R. Lewis and Christos H. Papadimitriou, Symmetric space-bounded computation; Theoretical Computer Science 19 (1982); pp. 161--187
  29. Ashok K. Chandra, Harry R. Lewis, and Johann Makowsky, Embedded implicational dependencies and their inference problem; Proceedings of 13th ACM Symposium on Theory of Computing, 1981; pp. 342--354
  30. Larry Denenberg and Harry R. Lewis, A hard problem for NTIME(n^k); Proceedings of the 1981 Allerton Conference; August, 1981
  31. Yuri Gurevich and Harry R. Lewisl, The inference problem for template dependencies, preliminary version; Proceedings of ACM SIGACT-SIGMOD Symposium on Principles of Database Systems; Los Angeles, 1982
  32. Yuri Gurevich and Harry R. Lewis, The inference problem for template dependencies; Information and Control 55 (1982); pp. 69--79
  33. Yuri Gurevich and Harry R. Lewis, The word problem for cancellation semigroups with zero; Journal of Symbolic Logic 49 (1984); pp. 184-191
  34. Harry R. Lewis and Richard Statman, Unifiability is complete for co-NLog space; Information Processing Letters 15 (1982); pp. 220-222
  35. Larry Denenberg and Harry R. Lewis, The complexity of the satisfiability problem for Krom formulas; Theoretical Computer Science 30 (1984); pp. 319-341
  36. Review of Garey and Johnson; Computers and Intractability: A Guide to the Theory of NP-Completeness, Journal of Symbolic Logic 48 (1983); pp. 498--500
  37. Larry Denenberg and Harry R. Lewis, Logical syntax and computational complexity; Computation and Proof Theory: Proceedings, Logic Colloquium Aachen 1983, Part II; Springer-Verlag Lecture Notes in Mathematics 1104 (1983), pp. 101-115
  38. Yuri Gurevich and Harry R. Lewis, A logic for constant-depth circuits; Information and Control 61 (1984); pp.65--74
  39. Harry R. Lewis and John H. Reif, Efficient symbolic analysis of programs; Journal of Computer and Systems Sciences 32 (1986); pp. 280-314
  40. Finite-state analysis of asynchronous circuits with bounded temporal uncertainty, TR-15-89; Harvard University, Center for Research in Computing Technology; 1989
  41. A logic of concrete time intervals; IEEE Conference on Logic in Computer Science (1990); p. 380
  42. Computing's Cranky Pioneer (review of I. Bernard Cohen's biography Howard Aiken and its companion volume Makin' Numbers); Harvard Magazine; May--June 1999
  43. Talented Eccentrics (review of Scott Rosenberg's book, Dreaming in Code), Harvard Magazine, March-April 2007.
  44. Digital Books, Inernational Journal of the Humanities, Vol. 7, no. 8, pp. 59--66.
  45. Renewing the Civic Mission of American Higher Education (with Ellen Condliffe Lagemann), in What is College For? The Public Purpose of Higher Education, Lagemann and Lewis, eds., Teachers College Press, 2011.
  46. The Internet and Hieronymus Bosch: Fear, Protection, and Liberty in Cyberspace, in The Harvard Sampler, Shephard, Kossly, and Hammonds, eds., Harvard University Press, 2011.
  47. After the Digital Explosion: Education and Civil Liberties in the Internet Age, in Teaching America, Feith, ed., Rowman & Littlefield, 2011.
  48. Protoball at Harvard: From Pastime to Contest,Base Ball, V. 5, no. 1 (Spring 2011), 41-45.
  49. Renewing the civic mission of American higher education (with Ellen Condliffe Lagemann), in What is Colelge For?, Lagemann and Lewis, eds, Teachers College Press, 2011,pp. 9-45.
  50. Lewis, Harry. The Internet and Hieronymus Bosch: Fear, Protection, and Liberty in Cyberspace, in Shephard, Kosslyn, and Hammonds, eds., The Harvard Sampler, Harvard University Press, 2011, pp. 57-90.
  51. Lewis, Harry. After the Digital Explosion: Education and Civil Liberties in the Internet Age, in Feith, David, ed., Teaching America: The Case for Civic Education, Rowman & Littlefield, 2011, 183-192.