## Outstanding Dissertations In The Computer Sciences

Haitham Hassanieh is the recipient of the ACM 2016 Doctoral Dissertation Award. Hassanieh developed highly efficient algorithms for computing the Sparse Fourier Transform, and demonstrated their applicability in many domains including networks, graphics, medical imaging and biochemistry. In his dissertation, The Sparse Fourier Transform: Theory and Practice, he presented a new way to decrease the amount of computation needed to process data, thus increasing the efficiency of programs in several areas of computing.

In computer science, the Fourier transform is a fundamental tool for processing streams of data. It identifies frequency patterns in the data, a task that has a broad array of applications. For many years, the Fast Fourier Transform (FFT) was considered the most efficient algorithm in this area. With the growth of Big Data, however, the FFT cannot keep up with the massive increase in datasets. In his doctoral dissertation Hassanieh presents the theoretical foundation of the Sparse Fourier Transform (SFT), an algorithm that is more efficient than FFT for data with a limited number of frequencies. He then shows how this new algorithm can be used to build practical systems to solve key problems in six different applications including wireless networks, mobile systems, computer graphics, medical imaging, biochemistry and digital circuits. Hassanieh’s Sparse Fourier Transform can process data at a rate that is 10 to 100 times faster than was possible before, thus greatly increasing the power of networks and devices.

Hassanieh is an Assistant Professor in the Department of Electrical and Computer Engineering and the Department of Computer Science at the University of Illinois at Urbana-Champaign. He received his MS and PhD in Electrical Engineering and Computer Science at the Massachusetts Institute of Technology (MIT). A native of Lebanon, he earned a BE in Computer and Communications Engineering from the American University of Beirut. Hassanieh’s Sparse Fourier Transform algorithm was chosen by *MIT Technology Review* as one of the top 10 breakthrough technologies of 2012. He has also been recognized with the Sprowls Award for Best Dissertation in Computer Science, and the SIGCOMM Best Paper Award.

Honorable Mention for the 2016 ACM Doctoral Dissertation Award went to Peter Bailis of Stanford University and Veselin Raychev of ETH Zurich.

In Bailis’s dissertation, Coordination Avoidance in Distributed Databases, he addresses a perennial problem in a network of multiple computers working together to achieve a common goal: Is it possible to build systems that scale efficiently (process ever-increasing amounts of data) while ensuring that application data remains provably correct and consistent? These concerns are especially timely as Internet services such as Google and Facebook have led to a vast increase in the global distribution of data. In addressing this problem, Bailis introduces a new framework, invariant confluence, that mitigates the fundamental tradeoffs between coordination and consistency. His dissertation breaks new conceptual ground in the areas of transaction processing and distributed consistency—two areas thought to be fully understood. Bailis is an Assistant Professor of Computer Science at Stanford University. He received a PhD in Computer Science from the University of California, Berkeley and his AB in Computer Science from Harvard College.

Raychev’s dissertation, Learning from Large Codebases, introduces new methods for creating programming tools based on probabilistic models of code that can solve tasks beyond the reach of current methods. As the size of publicly available codebases has grown dramatically in recent years, so has interest in developing programming tools that solve software tasks by learning from these codebases. Raychev’s dissertation takes a novel approach to addressing this challenge that combines advanced techniques in programming languages with machine learning practices. In the thesis, Raychev lays out four separate methods that detail how machine learning approaches can be applied to program analysis in order to produce useful programming tools. These include: code completion with statistical language models; predicting program properties from big code; learning program from noisy data; and learning statistical code completion systems. Raychev’s work is regarded as having the potential to open up several promising new avenues of research in the years to come. Raychev is currently a co-founder and Chief Technology Officer of DeepCode, a company developing artificial intelligence-based programming tools. He received a PhD in Computer Science from ETH Zurich. A native of Bulgaria, he received MS and BS degrees from Sofia University.

**SCS Student Awards**

School of Computer Science, Carnegie Mellon University

Pittsburgh PA 15213-3891

(412)268-8525 . (412)268-5576 (fax)

**School of Computer Science Distinguished Dissertation Award**

– Awarded annually by the School of Computer Science in recognition of outstanding work

by a graduate of our school-wide doctoral programs. The award includes a cash prize

and distinguished lectures by the recipient/s.

2016/2017 (Award 2017) 2015/2016 (Award 2016) 2014/2015 (Award 2015) 2013/2014 (Award 2014) 2012/2013 (Award 2013) 2011/2012 (Award 2012)

**Kanat Tanwongsan**, August 2011 (CS)*Efficient Parallel Approximation Algorithms*

–Advisors: Guy Blelloch, Anupam Gupta**Vijay Vasudevan**, October 2011 (CS)*Energy-efficient Data-intensive Computing with a Fast Array of Wimpy Nodes*

–Advisor: David Andersen__Honorable Mention__**André Filipe Torres Martins**, May 2011 (IST/Portugal)*The Geometry of Constrained Structured Prediction: Applications to*

Inference and Learning of Natural Language Syntax

–Advisors: Noah Smith, Eric Xing, Mário Figueiredo, Pedro Aguiar**Duen Horng**, July 2012 (ML)*Polo*Chau*Data Mining Meets HCI: Making Sense of Large Graphs*

–Advisor: Christos Faloutsos

2010/2011 (Award 2011)

**Jean-Francois Lalonde**, December 2011 (RI)*Understanding and Recreating Visual Appearance Under Natural Illumination*

–Advisors: Alexei Efros, Srinivasa Narasimhan__Honorable Mention__**Daniel Licata**, February 2011 (CS)*Dependently Typed Programming with Domain-Specific Logics*

–Advisor: Robert Harper**Hetunandan Kamisetty**, March 2011 (CS)*Structured Probabilistic Models of Proteins Across Spatial and Fitness Landscape*

–Advisors: Christopher J. Langmead, Eric P. Xing**Brian Ziebart**, December 2010 (ML)*Modeling Purposeful Adaptive Behavior with the Principle of Maximum Causal Entropy*

–Advisors: J. Andrew Bagnell, Anind K. Dey

2009/2010 (Award 2010)

**Yi Wu**, August 2010 (CS)*The Approximability of Learning and Constraint Satisfaction Programs*

–Advisor: Ryan O'Donnell__Honorable Mention__**Deepak Garg**, December 2009 (CS)*Proof Theory for Authorization Logic and Its Applications to a Practical File System*

–Advisor: Frank Pfenning

2008/2009 (Award 2019)

**Maria-Florina Balcan**, September 2008 (CS)*New Theoretical Frameworks for Machine Learning*

–Advisor: Avrim Blum__Honorable Mention__**Andreas Krause**, December 2008 (CS)*Optimizing Sensing: Theory and Applications*

–Advisor: Carlos Guestrin**Jurij Leskovec**, September 2008 (ML)*Dynamics of Large Networks*

–Advisor: Christos Faloutsos

2007/2008

**Derek Hoiem**, May 2007 (RI)*Seeing the World Behind the Image: Spatial Layout for 3D Scene Understanding*

–Advisors: Alexei (Alyosha) Efros and Martial Hebert__Honorable Mention__**Pradeep K. Ravikumar**, August 2007 (ML)*Approximate Inference Structure Learning and Feature Estimation in Markov Random Fields*

–Advisor: John Lafferty**Ryan Williams**, August 2007 (CS)*Algorithms and Resource Requirements for Fundamental Problems*

–Advisor: Manuel Blum

2006/2007

**Adam Wierman**, May 2007 (CS)*Scheduling for Today's Computer Systems: Bridging Theory and Practice*

–Advisor: Mor Harchol-Balter**Jacob O. Wobbrock**, July 2006 (HCII)*EdgeWrite: A Versatile Design for Text Entry and Control*

–Advisor: Brad A. Myers

2005/2006

**Luis Von Ahn**, December 2005 (CS)*Human Computation*

–Advisor: Manuel Blum

**Angela Demke Brown**, August 2005 (CS)*Explicit Compiler-based Memory Management for Out-of-core Applications*

–Advisor: Todd Mowry**Sanjit A. Seshia**, May 2005 (CS)*Adaptive Eager Boolean Encoding for Arithmetic Reasoning in Verification*

–Advisor: Randal E. Bryant

**Oley Mikhail Sheyner**, May 2004 (CS)*Scenario Graphs and Attack Graphs*

–Advisor: Jeannette Wing

**Michael H. Bowling**, May 2003 (CS)*Multiagent Learning in the Presence of Agents with Limitations*

–Advisors: Manuela Veloso**John Gregory Steffan**, September 2003*Hardware Support for Thread-Level Speculation*

–Advisors: Todd C. Mowry

**Robert C. Miller**, May 2002 (CS)*Lightweight Structure in Text*

–Advisors: Brad Myers and David Garlan**Perry S. Cheng**, September 2001 (CS)*Parallel, Real-Time Garbage Collection*

–Advisors: Guy Blelloch and Robert Harper

**Andrej Bauer**, December 2000 (CS)*DThe Realizability Approach to Computable Analysis and Topology*

–Advisor:Dana Scott**Robert W. O'Callahan**, May 2001 (CS)*Generalized Aliasing as a Basis for Program Analysis Tools*

–Advisors: Daniel Jackson and Jeannette Wing

**Carl Burch**, May 2000 (CS)*Machine Learning in metrical Task Systems and Other On-Line Problems*

–Advisor: Avrim Blum

**A. David Redish**, May 1997 (CS)*Beyond the Cognitive Map: Contributions to a Computational Neuroscience Theory of Rodent Navigation*

–Advisor: David Touretzky

**Jonathan R. Shewchuk**, May 1997 (CS)*Delaunay Refinement Mesh Generation*

–Advisors: Gary Miller and David O'Hallaron**Xudong Zhao**, August 1996 (CS)*Verification of Arithmetic Circuits*

–Advisor: Edmund Clarke

## One thought on “Outstanding Dissertations In The Computer Sciences”