Harry Roy Lewis

Gordon McKay Professor of Computer Science

Interim Dean, School of Engineering and Applied Sciences

Pierce Hall 217
School of Engineering and Applied Sciences
Harvard University
Cambridge, MA 02138

Home:
Six Hawes Street
Brookline, MA 02446

Voice (617)495-5829 for dean's business; permanent (617)496-2424 
email for dean's business: dean@seas.harvard.edu
email for professor business: lewis@harvard.edu
http://people.seas.harvard.edu/~lewis/
Curriculum Vitae

BOOKS

1. Unsolvable Classes of Quantificational Formulas;
   Addison-Wesley Publishing Company, Reading, Massachusetts, 1979
2. Harry R. Lewis and Christos H. Papadimitriou; Elements of the Theory of
   Computation; Prentice-Hall, Englewood Cliffs, New Jersey, 1981
3. An Introduction to Computer Programming and Data Structures
   using MACRO-11; Reston Publishing Company, Reston, Virginia, 1981
4. Harry R. Lewis and Larry Denenberg; Data Structures and their Algorithms;
   Harper Collins Publishers, Inc., New York, 1991
5. Harry R. Lewis and Christos H. Papadimitriou; STOCHEIA THEORIAS HYPOLOGISMOU ; Technical Chapter of Greece --- TEE, Athens, Greece, 1992. (Greek language edition of #2)
6. Harry R. Lewis and Christos H. Papadimitriou; Elements of the Theory of
   Computation, Second Edition; Prentice-Hall, Englewood Cliffs, New Jersey, 1997
7. Harry R. Lewis and Christos H. Papadimitriou; Elementos de Teoria da
   Computação, 2a Edição; Bookman, Porto Alegre, 2000 (Portuguese language edition of #6)
8. Harry R. Lewis, Excellence Without a Soul: How a Great University Forgot Education, PublicAffairs, 2006.
9. Paperback edition of #8, subtitled Does Liberal Education Have a Future?, 2007.
10. Chinese (both mainland and Taiwan) and Korean editions of #8.
11. Hal Abelson, Ken Ledeen, Harry Lewis, Blown to Bits: Your Life, Liberty, and Happiness After the Digital Explosion, Addison-Wesley, 2008.
12. Ataka Bitov (Russian translation of #11).
13. Chinese translation of #11.
14. Ellen Condliffe Lagemann and Harry R. Lewis, eds., What is College For? The Public Purpose of Higher Education, Teachers College Press, 2011. 
15. Education, Books, & Society: The Hong Kong Lectures, Chameleon Press, Hong Kong, 2011.
16. Baseball as a Second Language, Lulu, 2011.

OTHER PUBLICATIONS

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. How Facebook Spells the End of Privacy (Boston Globe, June 14, 2008)
    Inaccuracies In an Instant, Boston Herald, September 20, 2008
45. The Dangers of Internet Censorship, Boston Globe, November 5, 2008.
46. Not Your Father's Censorship, Chronicle of Higher Education, January 16, 2009.
47. The Internet and Hieronymus Bosch: Fear, Protection, and Liberty in Cyberspace, in The Harvard Sampler: Liberal Education for the Twenty-First Century, Jennifer M Shephard, Stephen Kosslyn, and Evelynn M. Hammonds, eds., Harvard University Press, 2011.
48. What Ails Elite Education? (Dialog with W. Deresiewicz) Chronicle of Higher Education,  August 19, 2014.
49. Anonymity and Reason, in Privacy in the Modern Age, Marc Rotenberg, Julian Horwitz, and Jermie Scott, eds., The New Press, 2015.
50. Report on the Structure of Harvard College (pdf); Committee Report; August, 1994.
51. Mission Statement, Harvard College; February 23, 1997
52. Romance and Love at Harvard, Harvard Crimson; February 12, 1.
53. Slow Down [advice to incoming freshmen, 2004 version] (7 pages); July 13, 2001
54. Harvard in America, a Year Later; Harvard Crimson; September 11, 2002
55. Harvard in a Beer-Ad World; Harvard Crimson; November 4, 2002
56. In Memory of Archie Epps; Harvard Crimson; September 12, 2003
57. Has Harvard lost its way? The Chronicle of Higher Education; The Chronicle Review, March 24, 2006.
58. Amateurism on and off the field, Harvard Crimson, April 21, 2006.
59. A Core Curriculum for Tomorrow's Citizens (Chronicle of Higher Education, September 7, 2007)
60. Copyright Harvard 2008 (Harvard Crimson, June 4, 2008)
61. The Winning Spirit, The Times (London), October 8, 2009.
62. Academe and the Decline of News Media, Chronicle of Higher Education, November 15, 2009.
63. Shrouded in Secrecy, Decision Makers Gambled and Harvard Lost, Boston Globe, December 12, 2009.
64. After the Digital Explosion: Education and Civil Liberties in the Internet Age, in Teaching America: The case for civic education, David Feith, ed., Rowman & Littlefield, 2011.
65. Renewing the Civic Mission of Higher Education, with Ellen Condliffe Lagemann, in What is College For, Teachers College Press, 2011.
66. Can the great American universities take root in Asia? South China Morning Post,  5 August 2013.
67. Mandela and Harvard, The Harvard Crimson,  11 December 2013.
68. Review of Burdens of Proof by Jean-François Blanchette, SIGACT News, March 2013, pp. 19-21.
69. Reinventing the Classroom, Harvard Magazine,  September-October, 2012.
70. Remembering Peter Gomes, Harvard Crimson, 26 May, 2011.
71. A national pastime with international meaning, South China Morning Post, 8 October 2011.
72. Grow Up! Review of Why Grow Up,  by Susan Neiman. Harvard Magazine, May-June, 2-14.

BLOG
I blog about developments in the world of digital information and society at bitsbook.com, a site associated with my book Blown to Bits.

SELECTED ADMINISTRATIVE COMMITTEES AT HARVARD, past and present

• Chair, Administrative Board of Harvard College (the body that grants exceptions to college rules and
  responds to infractions of those rules)
• Chair, Faculty Standing Committee on Athletic Sports
• Chair, Faculty Standing Committee on Advising and Counseling
• Chair, Committee on House Life
• Chair, Committee on College Life
• Faculty Standing Committee on Information Technology
• Faculty Standing Committee on Admissions and Financial Aid in Harvard College
• Faculty Standing Committee on Public Service
• Academic Deans of the Faculty of Arts and Sciences (the group that reviews all senior appointments to the Faculty)
• Faculty Council of the Faculty of Arts and Sciences (the steering committee for business of the Faculty)
• Committee on Undergraduate Education
• Educational Policy Committee
• Standing Committee on the Core Curriculum
• Harvard's Faculty Athletics Representative to the NCAA
• Harvard's Representative on the Ivy League Policy Committee
• Institutional representative to the Consortium on Financing Higher Education
• Chair, Commission of Inquiry, Faculty of Arts and Sciences
• Acting Chair, Core Curriculum Subcommittee on Quantitative Reasoning
• Co-Chair, Committee on the Structure of Harvard College (an Ad Hoc review committee during 1993--1994)}
• Committee on Graduate Education
• University Committee on Information Technology and Subcommittee on Intellectual Property (1996--1997)
• Committee to review Harvard's relation to the American Repertory Theatre (1996--1997)
• Board of Tutors in Applied Mathematics and in Computer Science (the governing boards of these undergraduate concentrations)
• Numerous search committees, including those for the Director of Admissions (1983), the Dean of Admissions and Financial Aid (1985), the Dean of Freshmen (1992), the Head Coach of Football (1994), the Director of Computer Services (1993), and the Director of Dining Services (1996)

• TEACHING 

I started teaching at Harvard in the fall of 1974, a decade before the university offered an undergraduate degree in Computer Science. I have therefore had the privilege of creating a number of the undergraduate courses in the field, and of teaching introductory computer science and theoretical computer science (especially foundations of computer science and algorithms) to thousands of students in aggregate.
In addition to teaching computer science, I have taught a general education course on social and legal issues precipitated by the digital revolution. I also teach a freshman seminar on Amateur Athletics, a study of the social history of sports in America and how it relates to fundamental American notions of fairness and equality and the dynamic of body, mind, and spirit.

BOARD MEMBERSHIPS 
Here are a few outside boards of which I am or have been a member.

• Computing Research Board, 1985-1988
• Trustee of the Roxbury Latin School, past board member and president.
• Trustee of the Charity of Edward Hopkins, 1995-2003
• Steering Committee, Harvard Advocates for ROTC