page_title: Harry R. Lewis
section_title: Research
hierarchical_section_title: Harry R. Lewis / Research
caption_attribution_description: Gordon McKay Professor of Computer Science en:Harry R. Lewis in his office in Maxwell Dworkin Hall, en:Harvard John A. Paulson School of Engineering and Applied Sciences
context_page_description: Harry Roy Lewis is an American computer scientist, mathe­ma­ti­cian, and uni­ver­sity admin­i­stra­tor known for his research in com­pu­ta­tional logic, textbooks in theoretical computer science, and writings on computing, higher education, and technology. He is 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 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.
  A new professorship in Engineering and Applied Sciences, endowed by a former student, will be named for Lewis and his wife upon their retirements.
context_section_description: Lewis' undergraduate thesis describing SHAPESHIFTER, "Two applications of hand-printed two-dimensional computer input", was written under computer graphics pioneer Ivan Sutherland
  and presented at the 23rd National Conference of the Association for Computing Machinery in 1968.
  It was followed by several papers on related topics.
  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.
  His 1979 book, Unsolvable classes of quantificational formulas
  complemented The Decision Problem: Solvable classes of quantificational formula by Dreben and Warren Goldfarb.
  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. The time for the sign reassignment in the original version of what Lindhorst and Shahrokhi called "this elegant result" was O (mn²) 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.
  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.Börger, Grädel, and Gurevich write that "this paper initiated the study of the complexity of decidable classes of the decision problem".
  "A logic of concrete time intervals" (1990) concerned temporal logic. 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.
  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.
  And his paper "Symmetric space-bounded computation" (1982, w
caption: Lewis in his office (2016)
exif: {}