Subhash Khot and Bill Thies named 2016 MacArthur Fellows
Subhash Khot, a theoretical computer scientist who has made significant contributions to computational complexity research, and Bill Thies, a computer scientist who has created communication and digital technologies to aid low-income communities, have been selected t as 2016 MacArthur Fellows.
Often called “genius grants,” each MacArthur Fellowship comes with an unrestricted grant of $625,000 paid out over five years. Fellowships are awarded in the sciences and the humanities and are intended to encourage people of outstanding talent to pursue their own creative, intellectual, and professional inclinations.
To celebrate Khot and Thies receiving this great honor, ACM has opened several of their important works. (See sidebar for links.)
Khot is best-known for his conception of Unique Games Conjecture. The conjecture has ushered in a useful way of addressing two of the most challenging and enduring questions in computational complexity theory: 1) How difficult is a problem to solve and 2) If you found the best method of solving the problem, how quickly could a computer find a solution using the method. A deeper understanding of the limitations of computing could have far-reaching impact and Khot’s insights have opened up fresh new avenues of exploration in this area.
Khot is an active ACM Professional Member. He received honorable mention in the ACM Doctoral Dissertation Award in 2003 and has published in several ACM publications including Journal of the ACM and proceedings of the Annual ACM Symposium on the Theory of Computing.
Bill Thies’s research focuses on the design and evaluation of technologies that contribute to the socio-economic development of low income communities with a focus on healthcare and education. 99 Dots,a new project he is championing, uses mobile phones and innovative packaging to monitor medication adherence. Based at Microsoft Research in India, Thies has been monitoring the effectiveness of the 99 Dots system for tuberculosis patients in rural India.
As Thies’s work draws on many sub-disciplines of computer science, he has participated in varied ACM conferences and events including Learning@Scale and the Annual ACM Symposium on Computing for Development. An active ACM member, Thies was an International co-winner, ACM SIGPLAN Outstanding Doctoral Dissertation Award in 2009.
To view the MacArthur Foundation’s citations for Khot and Thies, visit:
Subhash Khot's Top Five Downloaded Papers
- On the Power of Unique 2-prover 1-round Games, STOC '02: Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing
- Hardness of Approximating the Shortest Vector Problem in Lattices, Journal of the ACM (JACM)
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover, STOC '03: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing
- Unique Games on Expanding Constraint Graphs are Easy: Extended Abstract, Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing
- A New PCP Outer Verifier with Applications to Homogeneous Linear Equations and Max-bisection, STOC '04: Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing
- Subhash Khot's author page on the ACM Digital Library
William Thies's Top Five Downloaded Papers
- Designing Mobile Interfaces for Novice and Low-literacy Users, Transactions on Computer-Human Interaction (TOCHI)
- Exploiting Coarse-grained Task, Data, and Pipeline Parallelism in Stream Programs, ASPLOS XII: Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating
- A Stream Compiler for Communication-exposed Architectures, ASPLOS X: Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems
- Yours is Better!": Participant Response Bias in HCI, CHI '12: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems
- mClerk: Enabling Mobile Crowdsourcing in Developing Regions, CHI '12: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems
- William Thies's author page on the ACM Digital Library