Browse by award year
The Simons Foundation is proud to announce the 2015 grants to graduate students in theoretical computer science with outstanding track records of research accomplishments.
Prabhanjan Ananth, a Ph.D. candidate in computer science at the University of California, Los Angeles, received B.Eng and M.S. degrees from R. V. College of Engineering and the Indian Institute of Science in Bangalore, India, respectively. His research focuses on cryptographic program obfuscation. He has published at top venues including CRYPTO, TCC and ACM CCS. Among his recent results (joint with Jain) is a transformation that builds indistinguishability obfuscation from compact functional encryption. Another result (joint with Jain and Sahai) achieves the first construction of indistinguishability obfuscation with constant multiplicative size overhead.
Sarah Cannon earned a B.A. in mathematics at Tufts University in 2012 and an M.Sc. in mathematics and the foundations of computer science from the University of Oxford in 2013. Her current research as a Ph.D. student in the Algorithms, Combinatorics, and Optimization (ACO) program at the Georgia Institute of Technology studies randomized algorithms, with a focus on establishing provable bounds for the mixing time of Markov chains. Sarah has published numerous articles, spanning graph theory, computational geometry, self-assembly and Markov chains, typically involving planar geometry. For example, a recent result (SODA15) proved the existence of a phase transition for the mixing time of a local Markov chain on weighted dyadic tilings, a family of rectangular dissections. Sarah received an NSF Graduate Research Fellowship, a Clare Boothe Luce Outstanding Graduate Fellowship and was previously named a Computing Research Association Outstanding Undergraduate Researcher.
Rachel Cummings is a Ph.D. student in computing and mathematical sciences at the California Institute of Technology. She received B.A. degrees in mathematics and economics from the University of Southern California and her M.S. degree in computer science from Northwestern University. Her research interests lie in the intersection of computer science and economics, specifically problems surrounding algorithmic game theory, data privacy and learning theory. In one line of work, Cummings and her coauthors aim to understand what an observer can learn about an individual by repeatedly observing the individual making decisions, and how the individual can strategically make choices to obscure her or his true information. Cummings also works on designing markets for data, where individuals are compensated for their privacy loss and incentivized to truthfully report their data. She has published papers in the proceedings of EC, ITCS, AAAI, DISC and DNA. Her paper also received the best paper award at DISC 2014.
Mika Göös received his B.Sc. from Aalto University and his M.Sc. from the University of Oxford. He is currently a Ph.D. student at the University of Toronto, where his research focuses on communication complexity. Mika has over ten publications appearing in the top conferences/journals in theoretical computer science (PODC, STOC, JACM), including best student paper at PODC 2012 and best paper at DISC 2012. He has pioneered an approach in communication complexity where the complexity in the simpler query model is first established, and this result is then “lifted” to the world of communication complexity by proving a general transfer theorem. This approach has led Göös (and coauthors) to resolve several longstanding open problems in communication complexity, including Yannakakis’ clique versus independent set problem in communication complexity, improved monotone circuit depth lower bounds, stronger lower bounds for the log-rank conjecture, and a superlogarithmic separation between deterministic communication and partition number.
Justin Hsu is a Ph.D. student at the University of Pennsylvania, advised by Benjamin Pierce and Aaron Roth. He did his undergraduate work at Stanford, where he received a B.S. in mathematics with honors. Justin’s current research focuses on differential privacy, game theory and randomized algorithms, both from the perspective of algorithm design and from the perspective of formal verification. He has written more than 15 papers, published in venues like STOC and POPL. He has created new algorithms that substantially improve our understanding of and our ability to solve convex programming problems subject to differential privacy. He has also developed new tools to formally verify properties of randomized algorithms, including differential privacy and Bayesian Incentive Compatibility. His ongoing work focuses on (among other things) how to develop formal verification tools that will be amenable to verifying the kinds of arguments typically used in theory-A paper proofs, including independence of random variables and concentration of measure arguments.
Pravesh Kothari obtained his bachelor’s degree from the Indian Institute of Technology, Kanpur, and has been a Ph.D. student at the University of Texas at Austin since 2011. His research is focused on hardness of approximation, pseudorandomness and computational learning theory. His papers have appeared in major conferences such as STOC, SODA, CCC, COLT, NIPS and RANDOM. In a recent result with Boaz Barak and Siu On Chan, he proved an exponential lower bound on a large class of constraint satisfaction problems in the sum-of-squares SDP hierarchy. In another recent result, with Raghu Meka, he constructed almost optimal pseudorandom generators for spherical caps. In the past, in a paper with Adam Klivans and Igor Oliveira, he proved a tight relationship between proving circuit lower bounds and designing learning algorithms.
Mrinal Kumar is a Ph.D. student at Rutgers University. He received his B.Tech. in computer science from the Indian Institute of Technology, Madras. Mrinal’s research interests are in complexity theory, especially in lower bounds for arithmetic circuits. Over the last few years, he has made significant contributions to our understanding of “the method of shifted partial derivatives,” and has used this to prove long-elusive lower bounds on low-depth arithmetic circuit complexity. Mrinal also has interests in pseudorandomness and explicit constructions, and has made advances on polynomial identity testing and on “indexing” problems.
Euiwoong Lee is a Ph.D. student at Carnegie Mellon University, advised by Venkatesan Guruswami. He received his B.S. (2009) and M.S (2012) degrees from California Institute of Technology. Euiwoong is broadly interested in the approximate solvability of optimization problems, and his work has touched upon central topics in constraint satisfaction, graph theory, coding theory, game theory, combinatorial optimization and the power of linear/semidefinite programs. He has published in a variety of theoretical computer science conferences such as STOC, SODA, ITCS and EC. Euiwoong resolved a well-known open question on the approximability of a graph pricing problem where there are single-minded buyers each interested in a bundle of two items and the goal is to price items to maximize revenue. Euiwoong has also proved powerful hardness results for coloring hypergraphs that admit highly structured colorings. His work addresses all three aspects — algorithms, hardness and mathematical programming — that together bear upon the rich theory of approximability.
Henry Yuen is a Ph.D. student in the Theory of Computation group at MIT. He received his bachelor’s degree in mathematics and minor in computer science from the University of Southern California. His research focus concerns the rich interplay between quantum physics, computational complexity, communication complexity and information theory. Some of Yuen’s work has focused on the topic of quantum randomness expansion, whereby classical users can interact with untrusted quantum devices to force them to produce secure random bits. In one of his results, he showed that one only needs a constant amount of seed randomness to catalyze the production of an unlimited amount of output randomness. Recently, Yuen has been working on hardness amplification of quantum games.