What I Learned Today

I discovered two things today. The first was that most grad students don’t know about the ACM Distinguished Dissertation awards, which have been handed out every year since 1978 for the best Ph.D. theses in Computer Science. I think everyone who’s about to write a thesis ought to read at least one of these; they’re great models to follow, and you might even learn something.

The second thing I learned is that my professional organization doesn’t know from information architecture. I can forgive the awards’ site’s use of table-based layout—after all, I’m using it in this posting ;-). But would it really have been that hard to format the pages for the individual winners consistently, so that the little script I used to grab authors and titles didn’t have to be rewritten four times to handle all the egregiously-different cases? I also suspect that the pages were all built by hand, rather than being constructed from a database—the use of a URL in place of a thesis title in one case certainly suggests that.

Anyway, here they are: the best theses in Computer Science since 1978. Enjoy…

2005 Ben Liblit: Cooperative Bug Isolation
Honorable Mention Olivier Dousse: Asymptotic Properties of Wireless Multi-hop Networks
2004 Boaz Barak: Non-Black-Box Techniques in Cryptography
Honorable Mention Ramesh Johari: Efficiency Loss in Market Mechanisms for Resource Allocation
... Emmett Witchel: Mondriaan Memory Protection
2003 AnHai Doan: Learning to Map between Structured Representations of Data
Honorable Mention Dina Katabi: Decoupling Congestion Control
... Subhash Khot: New Techniques for Probabilistically Checkable Proofs and Inapproximability Results
2002 Venkatesan Guruswami: List Decoding of Error-Correcting Codes
Honorable Mention Robert C. Miller: Lightweight Structure in Text
... Tim Roughgarden: Selfish Routing
2001 Ion Stoica: Stateless Core: A Scalable Approach for Quality of Service
Honorable Mention Robert O'Callahan: Generalized Aliasing as a Basis for Program Analysis Tools
... David Wagner: Static Analysis and Computer Security
2000 Salil Vadhan: A Study of Statistical Zero-Knowledge Proofs
Honorable Mention William Chan: Symbolic Model Checking for Large Software Specifications
... Michael Ernst D.: Dynamically Discovering Likely Program
1999 Dieter van Melkebeek: Randomness and Completeness in Computational Complexity
1998 Hari Balakrishnan: Challenges To Reliable Data Transport Over Heterogeneous Wireless Networks
1997 Steven R. McCanne: Scalable Compression and Transmission of Internet Multicast Video
1996 Xiaoyuan Tu: Artificial Animals for Computer Animation: Biomechanics, Locomotion, Perception, and Behavior
Carl Waldspurger: Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management
1995 Sanjeev Arora: Probabilistic Checking of Proofs and Hardness of Approximation Problems
Dan Spielman: Computationally Efficient Error-Correcting Codes and Holographic Proofs
1994 David Karger: Random Sampling in Graph Optimization Problems
T.V. Raman: Audio System for Technical Readings
1993 Madhu Sudan: Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems
Honorable Mention James J. Kistler: Disconnected Operation in a Distributed File System
... Pandu Nayak: Automated Modeling of Physical Systems
1992 Kenneth McMillan: Symbolic Model Checking, An Approach to the State Explosion Problem
Mendel Rosenblum: The Design and Implementation of a Log-structured File System
1991 Robert Schapire: The Design and Analysis of Efficient Learning Algorithms
Series Winner Garth Gibson: Redundant Disk Arrays: Reliable, Parallel Secondary Storage
... Carsten Lund: The Power of Interaction
Honorable Mention Asit Dan: Performance Analysis of Data Sharing Environments
1990 Hector Geffner: Default Reasoning: Casual and Conditional Theories
David Heckerman: Probabilistic Similarity Networks
Series Winner Noam Nissan: Using Hard Problems to Create Pseudorandom Generators
1989 Vijay Saraswat: Concurrent Constraint Programming Languages
Series Winner Joe Killian: Uses of Randomness in Algorithms and Protocols
... Michael Kearns J.: The Computational Complexity of Machine Learning
1988 Mauricio Karchmer: Communication Complexity - A New Approach to Circuit Depth
Series Winner Anne Condon: Computational Models of Games
... David Dill: Trace Theory for Automatic Hierarchical Verification of Speed-Independent Circuits
1987 John Canny: The Complexity of Robot Motion Planning
Series Winner Marc H. Brown: Algorithm Animation
... Leslie Greengard: The Rapid Evaluation of Potential Fields in Particle Systems
1986 Ketan D. Mulmuley: Full Abstraction and Semantic Equivalence
Johan Torkel Hastad: Computational Limitations for Small Depth Circuits
Series Winner Carl Ebeling: All the Right Moves: A VLSI Architecture for Chess
... David Ungar: The Design and Evaluation of a High-Performance Smalltalk System
1985 John R. Ellis: Bulldog: A Compiler for VLIW Architecture
Series Winner Ben-Zion Chor: Two Issues in Public Cryptography, RSA Bit Security and a New Knapsack Type System
Daniel Hillis: The Connection Machine
1984 Manolis G.H. Katevenis: Reduced Instruction Set Computer Architecture for VLSI
Series Winner Carl E. Bach: Extended Riemann Hypothesis
... Henry Baird: Model-Based Image Matching Using Location
... James Korein: A Geometric Investigation of Reach
1983 Thomas W. Reps: Generating Language-Based Environments
Series Winner Ellen Hildreth: The Measurement of Visual Motion
... Steven Johnson: Synthesis of Digital Systems from Recursion Equations
1982 Charles E. Leiserson: Area-Efficient VLSI Computation
1980 Douglas Cook: The Evaluation of a Protection System
Ruth E. Davis: Generating Correct Programs from Logic Specifications
Lawrence Edwin Larson: Use of Decision Tables in Multi-Processing Environments
Jacob Slomin: Generalized Distributed Information Management Architecture
1978 Roderic G. Cattell: Formalization and Automatic Derivation of Code Generators
Joseph Urban: A Specification Language and Its Processor

In the wake of posts about Shopify's support for white nationalists and DataCamp's attempts to cover up sexual harassment
I have had to disable comments on this blog. Please email me if you'd like to get in touch.