Harry R. Lewis

Essentially all of Lewis's career has been at Harvard, where he has been honored for his "particularly distinguished contributions to undergraduate teaching"; his students have included future entrepreneurs Bill Gates and Mark Zuckerberg, and numerous future faculty members at Harvard and other schools. The website "Six Degrees to Harry Lewis", created by Zuckerberg while at Harvard, was a precursor to Facebook.

Education and career

A young man sits holding a microphone in his left hand while manipulating the console of an apparatus with his right. To his left a large television camera is trained on a large, circular cathode ray tube display.

Template:ShyTemplate:WbrTemplate:R/superscriptTemplate:Ran

Lewis was born in BostonTemplate:R/superscript and grew up in [[Wellesley, Massachusetts|Wellesley, Template:Shy]].Template:R/superscript His parents were physiciansTemplate:Sndhis father a hospital chief of anesthesiology and his mother the head of the Dever State School for [[Intellectual disability|Template:Shy disabled children]].Template:R/superscript His father was a World War II veteran and the son of a German Lutheran father and a Russian Jewish mother. After graduating summa cum laude at the end of the eleventh grade at Boston's Roxbury Latin School he entered Harvard College, where he was for a time a third-string lacrosse goalie.Template:R/superscript

Lewis has said that he discovered "I wasn't a real Template:Shy [once] I got out of the amateur leagues of high school mathematics", but was "tremendously excited" by the computer-science research Template:Shy at Harvard.Template:Ran As a senior he lectured a graduate class using a computer-graphics program, SHAPETemplate:ShySHIFTER, which he had developed for displaying complex-plane Template:Shy on a cathode ray tube. SHAPETemplate:ShySHIFTER automatically recognized formulas and commands hand-entered via a stylus on a RAND tablet, and could be "trained" to recognize the handwriting of individual users.Template:R/superscriptTemplate:R/superscript There being no degree program in computer science per se at Harvard at the time,Template:Ran in 1968 Lewis received his BA (summa, Quincy House) in applied mathematicsTemplate:R/superscriptTemplate:R/superscript and was elected to Phi Beta Kappa.Template:R/superscript

After serving for two years in the United States Public Health Service Commissioned Corps as a commissioned officer in the role of mathematician and computer scientist for the National Institutes of Health in Bethesda, Maryland, he spent a year in Europe as a Frederick Sheldon Traveling Fellow. He then returned to Harvard, where he earned his M.A. in 1973 and PhD in 1974, after which he was immediately appointed assistant professor of computer science. He became an associate professor in 1978, and Gordon McKay Professor of Computer Science in 1981.Template:R/superscript

Lewis formally retired in 2020,Template:R/superscriptTemplate:Refn but continues to teach as Gordon McKay Research Professor in Computer Science.Template:Refn His wife Marlyn McGrath retired in 2021 after 42 years as Harvard College's director of admissions.Template:Refn The Harry Lewis and Marlyn McGrath Professorship of Engineering and Applied Sciences was endowed by one of Lewis's former students in 2012.Template:R/superscriptTemplate:Refn

Teaching

Lewis has pointed out thatTemplate:Sndlargely because his career began when the field of computer science "barely existed", and Harvard offered almost no computer science courses at the undergraduate levelTemplate:Sndhe originated almost all the courses he has taught.Template:R/superscript It was his proposal, in the late 1970s, that Harvard create a major specifically for computer scienceTemplate:R/superscript (which until then had been a branch of Harvard's applied mathematics program).Template:Ran

From 2003 to 2008 he was designated a Harvard College Professor in recognition of "particularly distinguished contributions to undergraduate teaching".Template:R/superscript In 2021 the IEEE Computer Society awarded him its annual Mary Kenneth Keller Computer Science & Engineering Undergraduate Teaching Award, citing "his over forty-year dedication towards undergraduate computer science education at Harvard, his authoring of Computer Science introductory textbooks, and his mentoring of many future educators."Template:Refn

Six of his teaching assistantsTemplate:R/superscript are now members of the Harvard facultyTemplate:R/superscript and many others are professors of computer science (or related disciplines) elsewhere;Template:R/superscript many have gone on to win teaching awards themselves, including Eric Roberts (Association for Computing Machinery Karlstrom Award),Template:R/superscript Nicholas Horton (Robert V. Hogg Award),Template:R/superscript Joseph A. Konstan (University of Minnesota Distinguished University Teaching Professor, Graduate/Professional Teaching Award),Template:R/superscript and Margo Seltzer (Herchel Smith Professor of Computer Science at Harvard, Phi Beta Kappa teaching award, Abramson Teaching Award).Template:R/superscript

His undergraduate students have included Mark Zuckerberg (whose website "Six Degrees to Harry Lewis" was a precursor to FacebookTemplate:Sndsix degrees being a reference to the small world hypothesis),Template:Refn Microsoft founder Bill Gates (who solved an open theoretical problem Lewis had described in class),Template:Refn and nine future Harvard professors.Template:R/superscript

Lewis is the author or coauthor of five textbooks:

• An Introduction to Computer Programming and Data Structures using MACRO-11 (1981).Template:Ran MACRO-11 was an assembly language for PDP-11 computers.
• Elements of the Theory of Computation (1981, with Christos H. Papadimitriou)Template:Ran covers automata theory, computational complexity theory, and the theory of formal languages; its inclusion of complexity theory and mathematical logic was innovative for its time. It has been called an "excellent traditional text" but one whose terse and heavily mathematical style can be intimidating. Although intended for undergraduates, it has also been used for introductory graduate courses.
• Data Structures and Their Algorithms (1991, with Larry Denenberg).Template:Ran
• Essential Discrete Mathematics for Computer Science (2019, with Rachel Zax).Template:Refn
• Ideas that Created the Future (2021), a collection of "forty-six classic papers in computer science that map the evolution of the field."Template:Refn

Lewis has also taught a course on amateur athletics and the social history of sports in America.Template:R/superscript

Dean of Harvard College

File:HarryRLewis Harvard AppliedSciences11 TeachingFellows Halloween1982.jpg

Template:ShyTemplate:R/superscript

In 1994 Lewis coauthored the "comprehensive" Report on the Structure of Harvard College,Template:R/superscriptTemplate:R/superscript and in 1995Template:R/superscript he was appointed dean of Harvard College, responsible for the nonacademic aspects of undergraduate life.Template:R/superscript In that capacity he oversaw a number of sometimes-controversial policy changes, including changes to the handling of allegations of sexual assault, reorganization of the college's public-service programs, a crackdown on underage alcohol consumption, and random assignment of students to upperclass houses (countering the social segregation found under the prior system of assignment according to student preference).Template:RefnTemplate:R/superscriptTemplate:R/superscript He also pressed improvements to advising and health care.Template:R/superscriptTemplate:R/superscriptTemplate:R/superscript A colleague has said that Lewis "reshaped undergraduate life more powerfully than anyone else in recent memory."Template:R/superscript Lewis continued to teach throughout his time as dean.Template:R/superscript

After the 2001 inauguration of Harvard University's twenty-seventh president, Lawrence Summers, Lewis and Summers came into conflict over the direction of Harvard College and its educational philosophy.Template:R/superscriptTemplate:R/superscriptTemplate:R/superscriptTemplate:R/superscript Lewis, for example, emphasized the importance of extracurricular pursuits, advising incoming freshmen that "flexibility in your schedule, unstructured time in your day, and evenings spent with your friends rather than your books are all, in a larger sense, essential for your education", while Summers complained of an insufficiently intellectual "Camp Harvard" and admonished students that "You are here to work, and your business here is to learn."Template:R/superscriptTemplate:RanTemplate:Ran After Lewis issued what The Harvard Crimson called "a scathing indictment of the view that increasing intellectual rigor ought to be the [College's] priority"Template:Sndpointing out that prospective employers show less interest in grades than in personal qualities built outside the classroomTemplate:R/superscriptTemplate:Sndhe was peremptorily removed as dean in March 2003.Template:R/superscriptTemplate:R/superscriptTemplate:R/superscriptTemplate:R/superscript

In 2015 Lewis served as interim Dean of the Harvard School of Engineering and Applied Sciences.Template:R/superscript

Writings on education and technology

Lewis is a Faculty Associate of Harvard's Berkman Center for Internet & Society.Template:R/superscript In addition to his research publications and textbooks, he has written a number of works on higher education and the impact of computers on society.

Drawing heavily on his experience as dean of Harvard College, his Excellence Without A Soul: How a Great University Forgot Education (2006) critiques what he sees as the abandonment by American universities, including Harvard, of the

fundamental job of undergraduate education ... to turn eighteen- and nineteen-year-olds into twenty-one- and twenty-two-year-olds, to help them grow up, to learn who they are, to search for a larger purpose for their lives, and to leave college as better human beings.Template:Ran

In "Renewing the Civic Mission of American Higher Education" (with Ellen Condliffe Lagemann, 2012) Lewis warns that "a flourishing multiplicity of worthy but uncoordinated agendas has crowded out higher education's commitment to the common good":

Developed from a course taught by its authors, Blown to Bits: Your Life, Liberty, and Happiness After the Digital Explosion (2008, with Hal Abelson and Ken Ledeen) explores the origins and consequences of the 21st-century explosion in digital information, including its impact on culture and privacy:

It is now possible, in principle, to remember everything that anyone says, writes, sings, draws, or photographs. Everything ... Global computer networks can make it available to everywhere in the world, almost instantly. And computers are powerful enough to extract meaning from all that information, to find patterns and make connections in the blink of an eye.Template:Paragraph breakIn centuries gone by, others may have dreamed these things could happen, in utopian fantasies or in nightmares. But now they are happening.Template:Ran

Baseball as a Second Language: Explaining the Game Americans Use to Explain Everything Else (self-published as an experiment in open access in 2011)Template:R/superscript discusses the many ways baseball concepts and imagery have made their way into American English.Template:R/superscript It was inspired by Lewis' experiences explaining baseball to international students.Template:R/superscript

Research

File:HarryLewis Harvard OfficeKnickKnacks.jpg

Lewis in his office (2016)

Lewis' undergraduate thesis describing SHAPESHIFTER, "Two applications of hand-printed two-dimensional computer input",Template:Ran was written under computer graphics pioneer Ivan SutherlandTemplate:R/superscript and presented at the 23rd National Conference of the Association for Computing Machinery in 1968. It was followed by several papers on related topics.Template:R/superscript

Much of Lewis' subsequent research concerned the computational complexity of problems in mathematical logic. His doctoral thesis, "Herbrand Expansions and Reductions of the Decision Problem", was supervised by Burton Dreben and dealt with Herbrand's theorem.Template:R/superscriptTemplate:R/superscript His 1979 book, Unsolvable classes of quantificational formulasTemplate:Ran complemented The Decision Problem: Solvable classes of quantificational formula by Dreben and Warren Goldfarb.Template:R/superscript

His 1978 paper "Renaming a set of clauses as a Horn set" addressed the Boolean satisfiability problem, of determining whether a logic formula in conjunctive normal form can be made true by a suitable assignment of its variables. In general, these problems are hard, but there are two major subclasses of satisfiability for which polynomial time solutions are known: 2-satisfiability (where each clause of the formula has two literals) and Horn-satisfiability (where each clause has at most one positive literal). Lewis expanded the second of these subclasses, by showing that the problem can still be solved in polynomial time when the input is not already in Horn form, but can be put into Horn form by replacing some variables by their negations. The problem of choosing which variables to negate to make each clause get two positive literals, making the re-signed instance into a Horn set, turns out to be expressible as an instance of 2-satisfiability, the other solvable case of the satisfiability problem. By solving a 2-satisfiability instance to turn the given input into a Horn set, Lewis shows that the instances that can be turned into Horn sets can also be solved in polynomial time.Template:Ran The time for the sign reassignment in the original version of what Lindhorst and Shahrokhi called "this elegant result"Template:R/superscript was O

1. REDIRECT Template:Hair space

Template:Redirect category shell(mn²) for an instance with Template:Mvar clauses and Template:Mvar variables, but it can be reduced to linear time by breaking long input clauses into smaller clauses and applying a faster 2-satisfiability algorithm.Template:R/superscript

Lewis' paper "Complexity results for classes of quantificational formulas" (1980) deals with the computational complexity of problems in first-order logic. Such problems are undecidable in general, but there are several special classes of these problems, defined by restricting the order in which their quantifiers appear, that were known to be decidable. One of these special classes, for instance, is the Bernays–Schönfinkel class. For each of these special classes, Lewis establishes tight exponential time bounds either for deterministic or nondeterministic time complexity. For instance, he shows that the Bernays–Schönfinkel class is NEXPTIME-complete, and more specifically that its nondeterministic time complexity is both upper- and lower-bounded by a singly exponential function of the input length.Template:Ran Börger, Grädel, and Gurevich write that "this paper initiated the study of the complexity of decidable classes of the decision problem".Template:R/superscript

"A logic of concrete time intervals" (1990) concerned temporal logic.Template:Ran This paper accompanied an earlier Aiken Computation Laboratory technical report, "Finite-state analysis of asynchronous circuits with bounded temporal uncertainty", where he first proposed the representation of an asynchronous circuit, with bounded temporal uncertainty on gate transition events, as a finite-state machine. This paper was the earliest work on the verification of timing properties that modeled time both asynchronously and continuously, neither discretizing time nor imposing a global clock.Template:R/superscript

Some of Lewis' other heavily cited research papers extend beyond logic. His paper "Symbolic evaluation and the global value graph" (1977, with his student John Reif) concerned data-flow analysis and symbolic execution in compilers.Template:Ran And his paper "Symmetric space-bounded computation" (1982, with Christos Papadimitriou)Template:Ran was the first to define symmetric Turing machines and symmetric space complexity classes such as SL (an undirected or reversible analogue of nondeterministic space complexity, later shown to coincide with deterministic logarithmic space).Template:R/superscript In 1982, he chaired the program committee for the Symposium on Theory of Computing,Template:Ran one of the two top research conferences in theoretical computer science, considered broadly.Template:R/superscript

Personal

Lewis is a Visitor of Ralston College and a Life Trustee of the Roxbury Latin School.Template:R/superscript From 1995 to 2003 he was Trustee of the Charity of Edward Hopkins.Template:R/superscript The New York Times journalist David Fahrenthold is his son-in-law;Template:R/superscript while still a Harvard undergraduate, Fahrenthold wrote of his future father-in-law:

I've heard that if you sit out by the river [i.e. the Charles River] long enough, Dean of the College Harry R. Lewis '68 comes along and hands out computer science problem sets so you'll get back to work.Template:R/superscript

Selected publications

Computer science research

• Börger, Egon (1981). Review of Unsolvable classes of quantificational formulas. MRTemplate:Catalog lookup link.

Computers and society

• Interview with authors, Stanford Center for Internet and Society

Textbooks

• See in particular p. 205.

Higher education

Other

External links

• "Bits and Pieces" Lewis' blog
• "Blown to Bits" Lewis' old blog