CCC Update Landmark Contributions by Students in Computer Science

By CCC Update

Federal investment in university-based research produces the ideas and the people that make the United States the world leader in innovation.

If our nation wants researchers tomorrow, then our nation must support the education of researchers today. Educating researchers is commonly viewed as an apprenticeship process. Every Ph.D. dissertation breaks new ground, of course, but relatively few are game-changing. Through conducting Ph.D. research and writing a dissertation, the student learns how to conduct research, laying the foundation for a lifelong career.

Sometimes, though, students do work that truly is game-changing—they make landmark contributions that change the shape of the field. It’s interesting to take a look at some of these to appreciate them and to remind ourselves of the amazing things that students can achieve.

The list below was prepared by a half-dozen leaders in the computing research field, with input from a large number of colleagues. It comes with a host of caveats:

• Any such list is inevitably incomplete.
• It is constrained by the disciplinary knowledge of its creators.
• Individuals’ definitions of “landmark” will vary.
• No research ever stands alone: each researcher builds on the work of others, and each major contribution is subsequently amplified in important ways by others.
• This is a list of landmark contributions by students, not an authoritative history of various subfields.
• As it is difficult to predict how recent research will be viewed in the future, the list ends a decade ago.

If you’re willing add your suggestions, please go to the CCC Blog and nominate your favorite landmark contribution by a student:

• Use of Boolean logic to model digital circuits: Claude Shannon at MIT. Shannon is better known for inventing information theory, but this work, his MIT Masters thesis, was a landmark. (1937)
• Huffman coding: David Huffman at MIT. Huffman was a Ph.D. student when he invented Huffman coding as a term-paper project in a course taught by Robert M. Fano. (1951)
• Mathematical foundation of packet communication: Len Kleinrock at MIT. Kleinrock’s Ph.D. dissertation, Message Delay in Communication Nets with Storage, established a crucial foundation for the ARPANET revolution, in which he played a central role. (1962)
• Interactive computer graphics: Ivan Sutherland at MIT. Sutherland’s Sketchpad system—his Ph.D. work—laid the groundwork for several decades of advances in computer graphics. Ed Catmull’s 1974 Ph.D. dissertation, supervised by Sutherland at the University of Utah, was another landmark contribution to the field, as was John Warnock’s 16-page 1969 Ph.D. dissertation at the University of Utah attacking the hidden surface problem. (1963)
• Computer vision: Larry Roberts at MIT. Roberts is best known for his role in the ARPANET effort, but his 1963 MIT Ph.D. dissertation, Machine Perception of Three-Dimensional Solids, laid out the entire process for computer vision as we know it today. (1963)
• Symbolic mathematics: William A. Martin and Joel Moses at MIT. Martin’s 1967 Ph.D. dissertation on symbolic algebra and Moses’s 1967 Ph.D. dissertation on symbolic integration launched the MACSYMA project at MIT, the predecessor of today’s ubiquitous Mathematica. (1967)
• The FLEX language and machine: Alan Kay at the University of Utah. Kay's Ph.D. dissertation, The Reactive Engine, defined the FLEX language, the first extensible dynamic graphical interactive object-oriented language, and the direct antecedent of Kay's Smalltalk work at Xerox PARC. It also defined the FLEX machine, a desktop computer with a fully general display and a multiple clipping window user interface, the inspiration for Kay’s Dynabook. Kay says: "Most of us regarded what we were doing at PARC as 'phase two' of what we'd already started in graduate school." (1969)
• The Boyer-Moore theorem prover: Robert S. Boyer and J Strother Moore at the University of Edinburgh. Moore was a Ph.D. student and Boyer was a postdoctoral research associate. (1971)
• Efficient graph planarity testing using depth-first search: Bob Tarjan at Stanford. Tarjan’s thesis marked a crucial advance in the depth and elegance of the analysis of data structures for basic computational problems. (1972)
• Ethernet: Bob Metcalfe at Harvard. The engineering was done at Xerox PARC, but the invention and analysis of binary exponential backoff as an alternative to the fixed-backoff (and thus unstable) Aloha Network scheme was Metcalfe’s Ph.D. dissertation. (1973)
• BSD Unix: Bill Joy at Berkeley, working with Bob Fabry and Domenico Ferrari. (1977)
• VisiCalc: Bob Frankston and Dan Bricklin at MIT. The spreadsheet—the “killer app” for personal computing—was invented by Frankston and Bricklin while students at MIT, and sold through the company they formed, Software Arts. (1979)
• Public key cryptography: Ralph Merkle at Berkeley and Stanford, along with Martin Hellman and Whitfield Diffie. Merkle’s 1977 Berkeley Masters thesis and 1979 Stanford Ph.D. dissertation made fundamental contributions. Hellman maintains that the “Diffie-Hellman” key exchange protocol should be called “Diffie-Hellman- Merkle.” Public key certificates, as used ubiquitously in HTTPS-based web sites, were introduced in the 1978 MIT Bachelors thesis of Loren Kohnfelder, advised by Len Adleman of RSA fame. (1979)
• The Sun workstation: Andy Bechtolsheim at Stanford, working with Forest Baskett. (1982)
• The Connection Machine: Danny Hillis at MIT. Hillis co-founded the Thinking Machines Corporation while an MIT Ph.D. student. (1983)
• Sphinx (large-vocabulary, speaker-independent, continuous speech recognition): Kai-Fu Lee at Carnegie Mellon. While speech recognition has a long history both before and after Lee’s work, his Sphinx system, the subject of his Ph.D. dissertation, was a landmark. (1988)
• Linux: Linus Torvalds at the University of Helsinki. Torvalds was a second-year computer science student at the University of Helsinki when he launched the Linux open source operating system project, inspired by Andy Tanenbaum’s MINIX operating system and Richard Stallman’s GNU project. (1991)
• BDD-based symbolic model checking: Ken McMillan at Carnegie Mellon, working with Ed Clarke. Symbolic Model Checking (the title of McMillan’s Ph.D. dissertation) has transformed hardware and software verification. (1992)
• Mosaic: Mark Andreessen at the University of Illinois. Andreessen invented the revolutionary graphical Web browser while an undergraduate at the University of Illinois working at the National Center for Supercomputer Applications. He subsequently founded Netscape Communications. Microsoft licensed Mosaic from UIUC as the foundation for Internet Explorer. (1994)
• The PCP theorem: Sanjeev Arora at UC Berkeley. The PCP theorem (Probabilistically Checkable Proofs) is the cornerstone of the theory of computational hardness of approximation. (1994)
• Google: Larry Page and Sergey Brin at Stanford. The Page Rank algorithm is central to Google’s success. (Note that many earlier web search innovations were also due to students; for example, Brian Pinkerton at the University of Washington invented WebCrawler in 1994, the first successful full-text web search engine.) (1998)
• Akamai (content delivery networks): Danny Lewin at MIT, working with Tom Leighton. (1999)
• Peer-to-peer file sharing: Shawn Fanning at Northeastern University. Fanning was an undergraduate at Northeastern University when he wrote the code for Napster, inventing the concept of peer-to-peer file sharing, which has many important legal uses in addition to the questionable ones enabled by Napster. (1999)