Jump to content

Harry R. Lewis

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by EEng (talk | contribs) at 05:49, 1 April 2017 (Well,it's more complex than that.Though he oversaw the implementation,"he"didn't institute randomization;it was an essentially foregone conclusion given an earlier report recommending randomizing(though he had a big hand in that report, so...it's complex)). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

For other people named Harry Lewis, see Harry Lewis (disambiguation).
Harry R. Lewis
Born1947
Boston
NationalityAmerican
TitleGordon McKay Professor of Computer Science (1981–present)
Dean of Harvard College (1995–2003)
Harvard College Professor (2003–2008)
SpouseMarlyn McGrath (1968–present)[1]
Academic background
EducationRoxbury Latin School
Harvard University
ThesisHerbrand Expansions and Reductions of the Decision Problem (1974)
Doctoral advisorBurton Dreben
Academic work
DisciplineComputer science
Mathematical logic
Sub-disciplineDecidability
Theory of computation
InstitutionsHarvard School of Engineering and Applied Sciences
Notable students
Websitehttp://people.seas.harvard.edu/~lewis/

Harry Roy Lewis (born 1947)[1] is an American computer scientist, mathematician, and university administrator, known for his research in computational logic, textbooks in theoretical computer science, and writings on computing, higher education, and technology. He is the Gordon McKay Professor of Computer Science at Harvard University, and was Dean of Harvard College from 1995 to 2003.

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

Education and career

Lewis was born in Boston[2] and grew up in Wellesley, Massachusetts. His parents were physicians, his mother the head of a school for intellectually disabled children.[1] At the end of the eleventh grade he graduated summa cum laude from Boston's Roxbury Latin School, and in 1968 received his BA (summa) in applied mathematics from Harvard College,[1] where he was elected to Phi Beta Kappa[3] and was for a time a third-string lacrosse goalie.[4] As a senior he lectured a graduate course in applied mathematics using an early computer-graphics apparatus he had devised for visualizing mathematical concepts.[5]

After two years as a 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.[2][6] He became Assistant Professor of Computer Science at Harvard in 1974, Associate Professor in 1978, and has been Gordon McKay Professor of Computer Science since 1981.

As Dean of Harvard College (responsible for the nonacademic aspects of Harvard undergraduate life) from 1995 to 2003, he oversaw a number of sometimes-controversial policy changes. These included changes to procedures for handling allegations of sexual assault, reorganization of the college's public-service programs, a crackdown on underage alcohol use, and random assignment of students to upperclass houses (countering the social segregation found under the prior system of assignment according to student preference).[Note 1][1][7] He also continued to teach throughout his time as dean.[8] He served as interim Dean of the Harvard School of Engineering and Applied Sciences in 2015.[9]

He plans to retire in 2020,[10] at which time a new professorship in Engineering and Applied Sciences, endowed by a former student of Lewis, will be named for him and for his wife Marlyn McGrath, who is Harvard's director of admissions.[11]

Teaching

Lewis has pointed out that – largely because his career began at a time when the field of computer science "barely existed", and when Harvard offered almost no computer science courses at the undergraduate level – almost none of the courses he has taught existed until he created them.[12] From 2003 to 2008 he was designated a Harvard College Professor in recognition of "particularly distinguished contributions to undergraduate teaching."[8]

Many of his teaching assistants[13] have gone on to win teaching awards themselves, including Eric Roberts (Association for Computing Machinery Karlstrom Award),[14] Nicholas Horton (Robert V. Hogg Award),[15] Joseph A. Konstan (University of Minnesota Distinguished University Teaching Professor, Graduate/Professional Teaching Award),[16] and Margo Seltzer (Herchel Smith Professor of Computer Science at Harvard, Phi Beta Kappa teaching award, Abramson Teaching Award);[17] six are themselves now members of the Harvard faculty,[12] and many others are professors of computer science (or related disciplines) elsewhere.[18]

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 2] Microsoft founder Bill Gates (who solved an open theoretical problem Lewis had described in class),[23] and nine others who went on to become Harvard professors.[12]

Lewis is the author of two undergraduate textbooks. Elements of the Theory of Computation, written with Christos H. Papadimitriou,[LP] concerns automata theory, computational complexity theory, and the theory of formal languages;[24] its inclusion of complexity theory and mathematical logic was innovative for its time.[25] It has been called an "excellent traditional text" but one whose terse and heavily mathematical style can be intimidating.[24] Although intended for undergraduates, it has also been used for introductory graduate courses.[25] He wrote Data Structures and Their Algorithms with Larry Denenberg.[LD]

Writings on education and technology

Lewis is a Faculty Associate of Harvard's Berkman Center for Internet & Society.[26] In addition to his research publications and textbooks, he has authored a number of works on higher education and the relationship between computers and society.

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.[L06]: xii [27][28][29]

He explored that problem further in What is College For? The Public Purpose of Higher Education (2012, coedited with Ellen Condliffe Lagemann), a collection of essays by Lewis, Lagemann, and others.[30][31][32][33]

With Hal Abelson and Ken Ledeen he wrote Blown to Bits: Your Life, Liberty, and Happiness After the Digital Explosion (2008),[ALL] which explores the origins and public consequences of the 21st-century explosion in digital information, including its impact on culture and privacy.[34][35] The book developed from a Harvard Core Curriculum course on quantitative reasoning taught by its authors.[36] Baseball as a Second Language (2011), reflecting on the many ways baseball concepts and imagery have insinuated themselves into American English,[37] was inspired by Lewis' experiences explaining baseball to international students and self-published as an experiment in open access.[38]

Research

Lewis' undergraduate thesis, "Two applications of hand-printed two-dimensional computer input"[39] dealt with handwriting recognition, the parsing of handwritten mathematics, and their application to experimental mathematics. It was written under computer graphics pioneer Ivan Sutherland[2] and was followed by several papers on related topics.[40]

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.[2][41] His 1979 book, Unsolvable classes of quantificational formulas[L79][42] complemented The Decision Problem: Solvable classes of quantificational formula by Dreben and Warren Goldfarb;[43] together these works surveyed what was known on the subject as well as presenting new results.[44]

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 assigning a sign to each variable in such a way that no two variables end up as positive in the same clause as each other, 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.[L78] The time for the sign reassignment in the original version of what Lindhorst and Shahrokhi called "this elegant result"[45] was O (mn2) for an instance with m clauses and n variables, but it can be reduced to linear time by breaking long input clauses into smaller clauses and applying a faster 2-satisfiability algorithm.[46]

Lewis's 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.[L80] Börger, Grädel, and Gurevich write that "this paper initiated the study of the complexity of decidable classes of the decision problem".[47]

Some of Lewis's more heavily cited research papers extend beyond logic or complexity. His paper "Symbolic evaluation and the global value graph" (1977, with his student John Reif) concerned data-flow analysis and symbolic execution in compilers.[RL] His paper "Symmetric space-bounded computation" (1982, with Christos Papadimitriou)[LP82] was the first to define symmetric Turing machines and symmetric space complexity classes such as SL. SL is an undirected or reversible analogue of nondeterministic space complexity, later shown to coincide with deterministic logarithmic space.[48] And his paper "A logic of concrete time intervals" (1990) concerned temporal logic.[L90] In 1982, he was the chair of the program committee for the Symposium on Theory of Computing,[STOC] one of the two top research conferences in theoretical computer science, considered broadly.[49]

Personal

Lewis is a Visitor of Ralston College and a Life Trustee of the Roxbury Latin School.[50] From 1995 to 2003 he was Trustee of the Charity of Edward Hopkins.[2] Washington Post journalist David Fahrenthold is his son-in-law;[51] while still a student, Fahrenthold wrote of his future father-in-law:

I've heard that if you sit out by the 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.[52]

Notes

  1. ^ See Harvard College § House system.
  2. ^ In 2004 Zuckerberg wrote to Lewis,

    Professor, I've been interested in graph theory and its applications to social networks for a while now, so I did some research ... that has to do with linking people through articles they appear in from [The Crimson, the Harvard student newspaper]. I thought people would find this interesting, so I've set up a preliminary site that allows people to find the connection (through people and articles) from any person to the most frequently mentioned person in the time frame I looked at. That person is you.

    I wanted to ask your permission to put this site up though, since it has your name in its title.

    After some discussion Lewis gave his approval: "Sure, what the hell. Seems harmless."[19][20][21][22]

Selected publications

Books

L79.
Unsolvable classes of quantificational formulas (Addison-Wesley, 1979)[42][44]
LP81.
Elements of the Theory of Computation (with Christos H. Papadimitriou, first ed., Prentice-Hall, 1981; 2nd ed., 1997; numerous translations)[25]
LD.
Data Structures and Their Algorithms (with Larry Denenberg, Addison-Wesley, 1997)
L06.
ALL.
Blown to Bits: Your Life, Liberty, and Happiness After the Digital Explosion (Addison-Wesley, 2008, with Hal Abelson and Ken Ledeen; also on archive.org and translated into Chinese and Russian)[34][35]
L11a.
Education, Books, & Society in the Information Age: The Hong Kong Lectures (Chameleon Press, 2011)
L11b.
Baseball as a Second Language (self-published, 2011)[37]

Edited volumes

STOC.
Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing (Association for Computing Machinery, 1982)
LL.
What is College For? The Public Purpose of Higher Education (with Ellen Condliffe Lagemann, Teachers College Press, 2011)[30][31][32][33]

Research articles

RL.
Reif, John H.; Lewis, Harry R. (1977). "Symbolic evaluation and the global value graph". Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL '77). New York: ACM. pp. 104–118. doi:10.1145/512950.512961.
L78.
Lewis, Harry R. (1978). "Renaming a set of clauses as a Horn set". Journal of the ACM. 25 (1): 134–135. doi:10.1145/322047.322059. MR 0468315.
L80.
Lewis, Harry R. (1980). "Complexity results for classes of quantificational formulas". Journal of Computer and System Sciences. 21 (3): 317–353. doi:10.1016/0022-0000(80)90027-6. MR 0603587. A preliminary version of this work was presented as "Complexity of solvable cases of the decision problem for the predicate calculus" at the Symposium on Foundations of Computer Science, 1978.
LP82.
Lewis, Harry R.; Papadimitriou, Christos H. (1982). "Symmetric space-bounded computation". Theoretical Computer Science. 19 (2): 161–187. doi:10.1016/0304-3975(82)90058-5. MR 0666539. A preliminary version of this paper was presented at the International Colloquium on Automata, Languages and Programming, 1980.
L90.
Lewis, Harry R. (1990). "A logic of concrete time intervals (extended abstract)". Fifth Annual IEEE Symposium on Logic in Computer Science (Philadelphia, PA, 1990). Los Alamitos: IEEE Computer Society Press. pp. 380–389. doi:10.1109/LICS.1990.113763. MR 1099190.

Other

L09.
"Digital Books". International Journal of the Humanities. 7 (8): 59–66. 2009.
L11c.
"The Internet and Hieronymus Bosch: Fear, Protection, and Liberty in Cyberspace" in Shephard, Jennifer M.; Kosslyn, Stephen Michael; Hammonds, Evelynn Maxine (2011). The Harvard Sampler: Liberal Education for the Twenty-First Century. Harvard University Press. pp. 57–90. ISBN 978-0-674-05902-3.

References

  1. ^ a b c d e Bradley, Richard (2005). Harvard rules: the struggle for the soul of the world's most powerful university (1st ed.). HarperCollins. pp. 238–242. ISBN 0-06-056854-2.
  2. ^ a b c d e "Harry Lewis curriculum vitae". Lewis.seas.harvard.edu. Retrieved 2017-03-21.
  3. ^ "PBK Elects". The Crimson. November 16, 1967.
  4. ^ Rochelson, David B. "Lewis Defended University Athletics | News | The Harvard Crimson". Thecrimson.com. Retrieved 2017-03-21.
  5. ^ Kramer, Joel R. (November 9, 1967). "Computer Stops Counting, Draws". Harvard Crimson.
  6. ^ "Harry R. Lewis | Harvard John A. Paulson School of Engineering and Applied Sciences". Seas.harvard.edu. Retrieved 2017-03-21.
  7. ^ Macmillan, Valerie J. (January 31, 1996). "Lewis' Trying Term". Harvard Crimson.
  8. ^ a b McGreevey, Sue. "Five teachers honored with Harvard College Professorships | Harvard Gazette". News.harvard.edu. Retrieved 2017-03-21.
  9. ^ "A new dean for SEAS | Harvard John A. Paulson School of Engineering and Applied Sciences". Seas.harvard.edu. 2015-05-14. Retrieved 2017-03-21.
  10. ^ Debenedictis, Julia E. (February 28, 2017). "Harry Lewis To Retire After 46 Years". Harvard Crimson.
  11. ^ "I Choose Harvard: Laurence Lebowitz '82, MBA'88 | Stories | Harvard Alumni". Alumni.harvard.edu. 2017-03-17. Retrieved 2017-03-21.
  12. ^ a b c Lewis, Harry R. (March 1, 2017). "An odd fact about my teaching career". Bits and Pieces.
  13. ^ "Teaching Fellows | Harry R. Lewis". Lewis.seas.harvard.edu. Retrieved 2017-03-21.
  14. ^ "ACM Karl V. Karlstrom Outstanding Educator Award - Award Winners: Alphabetical Listing". Awards.acm.org. Retrieved 2017-03-21.
  15. ^ "SIGMAA on Statistics Education". Sigmaa.maa.org. Retrieved 2017-03-21.
  16. ^ "Award for Outstanding Contributions to Postbaccalaureate, Graduate, and Professional Education". Scholars Walk. University of Minnesota. March 6, 2017. Retrieved 2017-03-21.
  17. ^ "Margo I. Seltzer | Harvard John A. Paulson School of Engineering and Applied Sciences". Seas.harvard.edu. Retrieved 2017-03-21.
  18. ^ Lewis, Harry R. (October 4, 2012). "A 30th Anniversary Family Photo". Bits and Pieces.
  19. ^ Tanner, Adam (2014). "The Puzzle of Your Identity: Six Degrees to Harry Lewis". What Stays in Vegas: The World of Personal Data—Lifeblood of Big Business—and the End of Privacy as We Know It. PublicAffairs. p. 97. ISBN 9781610396394.
  20. ^ Kirkpatrick, David (2010). The Facebook Effect: The Inside Story of the Company That Is Connecting the World. Simon and Schuster. p. 26. ISBN 9781439109809. He also wrote a program he called "Six Degrees of Harry Lewis", an homage to a favorite computer science professor.
  21. ^ Lewis, Harry R. (November 7, 2011). "My Real Contribution to the Birth of Facebook". Bits and Pieces.
  22. ^ Lewis, Harry R. (May 19, 2012). "My REAL Contribution to the Birth of Facebook (II)". Bits and Pieces.
  23. ^ Kestenbaum, David (July 4, 2008). "Before Microsoft, Gates Solved A Pancake Problem". National Public Radio.
    Gates, William H.; Papadimitriou, Christos H. (1979). "Bounds for sorting by prefix reversal" (PDF). Discrete Mathematics. 27 (1): 47–57. doi:10.1016/0012-365X(79)90068-2.
  24. ^ a b Greenleaf, Newcomb. "Bringing mathematics education into the algorithmic age". In Myers, J. Paul, Jr.; O'Donnell, Michael J. (eds.). Constructivity in Computer Science: Summer Symposium San Antonio, TX, June 19–22, 1991, Proceedings. Lecture Notes in Computer Science. Vol. 613. Springer. pp. 199–217. doi:10.1007/bfb0021092.{{cite conference}}: CS1 maint: multiple names: editors list (link) See in particular p. 205.
  25. ^ a b c Gallier, Jean H. (September 1984). "Review: Elements of the Theory of Computation by Harry R. Lewis; Christos H. Papadimitriou". Journal of Symbolic Logic. 49 (3): 989–990. doi:10.2307/2274157.
  26. ^ "People | Berkman Klein Center". Cyber.law.harvard.edu. Retrieved 2017-03-21.
  27. ^ a b Sleeper, Jim (May 28, 2006). "Examining the Crimson's civic slide". Boston Globe.
  28. ^ a b Shea, Christopher (July 2, 2006). "Poison Ivy: A Harvard man urges the school to redefine its mission". Washington Post.
  29. ^ a b Gasarch, William (2007). "Review of Excellence Without a Soul" (PDF). The Book Review Column. ACM SIGACT News. 38 (1): 9–13. doi:10.1145/1233481.1233486.
  30. ^ a b Ream, Todd C. (Spring 2013). "What Is College For? The Public Purpose of Higher Education". The Review of Higher Education. 36 (3): 427–429.
  31. ^ a b Cecil, Kyle (2014). "What Is College For? The Public Purpose of Higher Education". Journal of Higher Education Outreach and Engagement. 18 (2): 307–312.
  32. ^ a b Bettencourt, Genia M.; Kimball, Ezekial (2015). "Book Review: What is College For? The Public Purpose of Higher Education". Journal of Student Affairs Research and Practice. 52 (2): 234–236. doi:10.1080/19496591.2015.1018271.
  33. ^ a b Rawls, Kristin (October 12, 2012). "10. 'What Is College For? The Public Purpose of Higher Education,' edited by Ellen Condliffe Lagemann and Harry Lewis". 10 must-read books about higher education in America. Christian Science Monitor.
  34. ^ a b Gasarch, William (2009). "Review of Blown to Bits" (PDF). The Book Review Column. ACM SIGACT News. 40 (1): 10–13. doi:10.1145/1515698.1515701.
  35. ^ a b Tanaka Okopnik, Kat (August 31, 2008). "Book Review: Blown to Bits". Linux Gazette. No. 154. {{cite magazine}}: Cite has empty unknown parameter: |1= (help)
  36. ^ "Off the Shelf: Recent books with Harvard connections". Harvard Magazine. July–August 2008.
  37. ^ a b "Lingua Branca: Harry Lewis explains how baseball explains everything". John Harvard's Journal. Harvard Magazine. March–April 2012.
  38. ^ Lewis, Harry R. (August 18, 2011). "Baseball as a Second Language". Bits and Pieces.
  39. ^ Lewis, Harry R. (1968). Two applications of hand-printed two-dimensional computer input, Bachelor's thesis, Harvard University.
  40. ^ "SHAPESHIFTER: An interactive program for experimenting with complex-plane transformations"; Proceedings of the 23rd National Conference of the Association for Computing Machinery, 1968; pp. 717--724
    "An interactive graphics facility under the PDP-10/50 timesharing monitor"; Proceedings of the DECUS Fall 1969 Conference; pp. 59--62
    "Techniques for generating, manipulating, and storage management of type 340 display files"; Proceedings of the DECUS Fall 1969 Conference; pp. 67--74
    "A device to make a Rand tablet act like a light pen"; Proceedings of the DECUS Spring 1970 Conference; pp. 249--251 (with Malcolm C. Bruce)
  41. ^ Harry Roy Lewis at the Mathematics Genealogy Project
  42. ^ a b Börger, Egon (1981). Review of Unsolvable classes of quantificational formulas. MR0544668.
  43. ^ Dreben, Burton; Goldfarb, Warren D. (1979). The decision problem: solvable classes of quantificational formulas. Addison-Wesley.
  44. ^ a b Gurevich, Yuri (1982). "Book Review: The decision problem: Solvable classes of quantificational formulas // Book Review: Unsolvable classes of quantificational formulas". American Mathematical Society. New Series. 7 (1): 273–277. doi:10.1090/S0273-0979-1982-15033-9. MR 1567367.
  45. ^ Lindhorst, Greg; Shahrokhi, Farhad (1989). "On renaming a set of clauses as a Horn set". Information Processing Letters. 30 (6): 289–293. doi:10.1016/0020-0190(89)90229-9. MR 0994523.
  46. ^ Aspvall, Bengt (1980). "Recognizing disguised NR(1) instances of the satisfiability problem". Journal of Algorithms. 1 (1): 97–103. doi:10.1016/0196-6774(80)90007-3. MR 0578079.
  47. ^ Börger, Egon; Grädel, Erich; Gurevich, Yuri (1997), The classical decision problem, Perspectives in Mathematical Logic, Berlin: Springer-Verlag, p. 456, doi:10.1007/978-3-642-59207-2, ISBN 3-540-57073-X, MR 1482227
  48. ^ Moore, Cristopher; Mertens, Stephan (2011). "8.10 Symmetric space". The nature of computation. Oxford University Press, Oxford. doi:10.1093/acprof:oso/9780199233212.001.0001. ISBN 978-0-19-923321-2. MR 2849868.
  49. ^ Fich, Faith (1996). "Infrastructure issues related to theory of computing research". ACM Computing Surveys. 28 (4es): 217. doi:10.1145/242224.242502..
  50. ^ "Our Trustees". Roxburylatin.org. Retrieved 2017-03-21.
  51. ^ "Elizabeth Lewis and David Fahrenthold". The New York Times. August 21, 2005. Retrieved December 3, 2016.
  52. ^ Fahrenthold, David A. (May 22, 2000). "A Vision of the Future". The Harvard Crimson.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Harry_R._Lewis&oldid=773239010"