[8] His parents were physicians – his father a hospital chief of anesthesiology and his mother the head of the Dever State School for intel­lec­tu­ally disabled children.

[10] 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.

[8] Lewis has said that he discovered "I wasn't a real math­e­ma­ti­cian [once] I got out of the amateur leagues of high school mathematics", but was "tremendously excited" by the computer-science research oppor­tu­nities at Harvard.

[L2] As a senior he lectured a graduate class using a computer-graphics program, SHAPE­SHIFTER, which he had developed for displaying complex-plane trans­for­ma­tions on a cathode ray tube.

[6][11] There being no degree program in computer science per se at Harvard at the time,[L2] in 1968 Lewis received his BA (summa, Quincy House) in applied mathematics[5][12] and was elected to Phi Beta Kappa.

[29] His undergraduate students have included Mark Zuckerberg (whose website "Six Degrees to Harry Lewis" was a precursor to Facebook – six degrees being a reference to the small world hypothesis),[Note 5] Microsoft founder Bill Gates (who solved an open theoretical problem Lewis had described in class),[Note 1] and nine future Harvard professors.

[35] 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).

[5][40][33][41] 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.

"[42][L06]: 86–90 [L1] 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" – pointing out that prospective employers show less interest in grades than in personal qualities built outside the classroom[40] – he was peremptorily removed as dean in March 2003.

[45] 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.

[LL]: 10-11  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.

And computers are powerful enough to extract meaning from all that information, to find patterns and make connections in the blink of an eye.In centuries gone by, others may have dreamed these things could happen, in utopian fantasies or in nightmares.

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.

[L80] Börger, Grädel, and Gurevich write that "this paper initiated the study of the complexity of decidable classes of the decision problem".