Aaron Sidford

Julian Shun has won the 2015 ACM Doctoral Dissertation Award presented by ACM for providing evidence that, with appropriate programming techniques, frameworks and algorithms, shared-memory programs can be simple, fast and scalable. In his dissertation Shared-Memory Parallelism Can Be Simple, Fast, and Scalable, he proposes new techniques for writing scalable parallel programs that run efficiently both in theory and in practice.

While parallelism is essential to achieving high performance in computing, writing efficient and scalable programs can be very difficult. Shun’s three-pronged approach to writing parallel programs that he outlines in his thesis includes:

1. proposing tools and techniques for deterministic parallel programming;
2. the introduction of Ligra, the first high-level shared-memory framework for parallel graph traversal algorithms; and
3. presenting new algorithms for a variety of important problems on graphs and strings that are both efficient in theory and practice.

Shun is a post-doctoral researcher at the University of California, Berkeley, where he was awarded a Miller Research Fellowship. He earned his Ph.D. at Carnegie Mellon University, which nominated him for the ACM Doctoral Dissertation Award. He earned a B.A. in Computer Science from the University of California, Berkeley, where he was ranked first in the 2008 graduating class of computer science students. During the 2013-2014 academic year, he was the recipient of a Facebook Graduate Fellowship.

He will receive the Doctoral Dissertation Award and its $20,000 prize at the annual ACM Awards Banquet on June 11 in San Francisco. Financial sponsorship of the award is provided by Google Inc.

Honorable Mention

Honorable mention for the 2015 ACM Doctoral Dissertation Award went to Aaron Sidford of the Massachusetts Institute of Technology, and Siavash Mirarab of the University of Texas at Austin. They will share a $10,000 prize, with financial sponsorship provided by Google Inc.

In Sidford’s dissertation, Iterative Methods, Combinatorial Optimization, and Linear Programming Beyond the Universal Barrier, he considers the fundamental problems in continuous and combinatorial optimization that occur pervasively in practice, and shows how to improve upon the best-known theoretical running times for solving these problems across a broad range of parameters. Sidford uses and improves techniques from diverse disciplines including spectral graph theory, numerical analysis, data structures, and convex optimization to provide the first theoretical improvements in decades for multiple classic problems ranging from linear programming to linear system solving to maximum flow. Sidford is presently a postdoctoral researcher at Microsoft New England. He received a Ph.D. in Computer Science from the Massachusetts Institute of Technology, which nominated him for this award.

Mirarab’s dissertation, Novel Scalable Approaches for Multiple Sequence Alignment and Phylogenomic Reconstruction, addresses the growing need to analyze large-scale biological sequence data efficiently and accurately. To address this challenge, Mirarab introduces several methods: PASTA, a scalable and accurate algorithm that can align data sets up to one million sequences; statistical binning, a novel technique for reducing noise in estimation of evolutionary trees for individual parts of the genome; and ASTRAL, a new summary method that can run on 1,000 species in one day and has outstanding accuracy. These methods were essential in analyzing very large genomic datasets of birds and plants. Mirarab is currently an Assistant Professor of Electrical and Computer Engineering at the University of California, San Diego. He obtained a Ph.D. in Computer Science from the University of Texas at Austin, which nominated him for this award.