Browse by award year
The Simons Foundation is proud to announce the 2014 grants to graduate students in theoretical computer science with outstanding track records of research accomplishments.
Aaron Bernstein, a Ph.D. candidate in computer science at Columbia University, received a B.S. in mathematics from MIT in 2009. His research focuses on dynamic graph algorithms, that is, problems in which a graph is changing over time, and one wants to efficiently update the graph and query the graph for various information. He has several results on the dynamic all-pairs shortest paths problem, showing that as edges are added and deleted, we can quickly update all the distances in the graph without having to recompute them from scratch. To obtain these results, he has developed a general framework that borrows techniques from spanner and emulator theory in order to effectively compress an arbitrary graph, allowing faster and simpler operations. He has published papers in the top conferences in theoretical computer science, STOC, FOCS and SODA, and received best student paper awards SODA 2010, SODA 2012, and STOC 2013. He is also the recipient of an NSF Graduate Research Fellowship and a Columbia Engineering Presidential Fellowship.
Ankit Garg received his bachelor’s degree from Indian Institute of Technology, Delhi, and is currently a Ph.D. student in the Theoretical Computer Science group at Princeton University. His research focuses on the applications of information theory in complexity theory, which is a growing area with connections to communication complexity, hardness amplification and the linear programming lower bounds. One of his papers obtained exact upper and lower bounds on the randomized communication complexity of a well-studied problem, set disjointness. Another paper developed a technique for obtaining information complexity lower bounds from communication complexity lower bounds in a black box manner. This paper won the best paper award at International Computer Science Symposium in Russia, 2013.
Mohsen Ghaffari is a Ph.D. student at MIT. He received B.S. degrees in electrical engineering (communications) and in computer science, both from Sharif University of Technology in Iran, and an M.S. degree in computer science from MIT. Mohsen has a broad interest in theory of computation; his current research revolves around distributed algorithms, graph algorithms, error-correcting codes for interactive communication, and algorithms for wireless networks. His research at MIT has led to 15 published papers in conferences such as STOC, SODA, PODC, DISC, ICALP, and received the best paper award of DISC 2013 and the best student paper award of ICALP 2014 (track C). Among his recent results are near-tight bounds on the decompositions of graph vertex connectivity, vertex connectivity under vertex-sampling, error-correcting codes for interactive communication with optimal tolerable error-rate and near-linear time computation.
Tengyu Ma has a bachelor’s degree from Tsinghua University and is currently a second-year graduate student at Princeton University. Previously he won a silver medal at the International Mathematical Olympiad and was ranked 8th at MAA’s Putman Competition. Ma’s work seeks to develop efficient algorithms with provable guarantees for machine learning problems. One of his works gives polynomial time algorithms for a class of deep neural networks in the generative model and reveals interesting structures of neural networks with random weights. In another work, Ma and his co-authors showed that dictionary learning/sparse coding can be solved provably by minimizing a certain non-convex function using alternating minimization as well as simple neurally plausible algorithms.
Jamie Morgenstern is a Ph.D. student at Carnegie Mellon University. She did her undergraduate work at the University of Chicago, where she received a B.S. with honors in computer science and a B.A. in mathematics. Morgenstern’s current research focuses on market algorithms, including auctions and fair division, as well as issues of learning and privacy which arise in mechanism design. She also works on approximation algorithms in bioinformatics. As one notable result, Morgenstern and her coauthors have shown, with a heterogeneous divisible good, there always exists an envy-free allocation with social welfare at least as high as the best equitable allocation. One of her current projects involves analyzing how providing privacy-preserving information about players’ actions can improve social welfare and avoid disastrous outcomes in natural multi-agent settings motivated by financial decision-making. She is also developing methods that can be used for learning preferences of bidders in auctions from only their final outcomes.
Valeria Nikolaenko received her B.S. degree from St. Petersburg State Polytechnic University and M.S. degree from the Academic University of the Russian Academy of Sciences. Valeria is currently a third-year Ph.D. student at Stanford University, working on cryptography with a focus on computing on encrypted data. Nikolaenko developed a new cryptographic primitive called ‘fully key-homomorphic encryption’ that has powerful applications to public-key cryptography and secure two-party computation. She also built practical systems for running machine learning algorithms on encrypted data. Her results appeared in major conferences in her area (IEEE S&P 2013, ACM CCS 2013, EUROCRYPT 2014).
David Rosenbaum is a Ph.D. student in computer science and engineering at the University of Washington. He received his bachelor’s degree in computer science and mathematics from Portland State University. His research interests span both classical and quantum computation, focusing on algorithms for isomorphism problems, quantum algorithms and quantum circuit architectures. His papers have been published in a variety of venues, including SODA, QIP, TQC, QIC, and PRA. He has developed new algorithms to test group isomorphism, both classical and quantum, including the first improvement in nearly four decades in the running time of algorithms to test isomorphism for general groups, as well as faster algorithms for the case of solvable groups. He has also developed an efficient way to simulate the abstract theoretical models of quantum circuits, which allow arbitrary pairwise interactions of quantum elements, via two-dimensional quantum computers using only local interactions.
Lior Seeman is a Ph.D. student at Cornell University and earned his bachelor’s degree in computer science and management from Tel Aviv University. His research lies at the intersection between computer science, economics, social science and cognitive science. More specifically, Seeman has been working on using ideas from computational complexity to model people’s bounded rationality, and using that to better understand their decision-making processes and social interaction. Seeman’s work has shown that modeling people as computationally bounded agents can help us better understand and predict their behavior. He has also studied how viewing agents as computationally bounded can affect our understanding of fundamental problems at the intersection of game theory and computer science, such as the complexity of computing Nash equilibrium in repeated games. Finally, Seeman also interned in Google research, where he developed a new approach for the well-studied problem of influence maximization in social networks, which takes advantage of some structural properties of the network. Seeman’s work has appeared in conferences such as FOCS, ITCS, AAAI and VLDB.
Xiaorui Sun is a Ph.D. student at Columbia University and received both his B.S. and M.S. in computer science from Shanghai Jiao Tong University. His research interests include graph isomorphism testing, computational machine learning and algorithmic game theory. His papers have been published in the proceedings of STOC, FOCS, SODA, CCC and EC. In two recent papers, he and his co-authors improved the isomorphism testing bound for strongly regular graphs as well as Steiner 2-designs. His other line of work in efficient distribution estimation resulted in a highly efficient ‘semi-agnostic’ algorithm for learning univariate probability distributions that are well approximated by piecewise polynomial density functions.
Christos Tzamos received his bachelor’s degree in electrical engineering and computer science from the National Technical University of Athens, Greece. He is currently a Ph.D. student in the Theory and Computation group at MIT working under the supervision of Constantinos Daskalakis. His research interests lie in the intersection of computer science and economics and include algorithmic game theory and mechanism design. Tzamos’s work aims at understanding the structure and computational complexity of revenue-optimal auctions, two central problems in the field of mechanism design. His work provides a general framework for identifying revenue-optimal auctions in different situations by connecting the problem of auction design to a seemingly unrelated field of mathematics, namely transportation theory. Tzamos has published several papers in the proceedings of general theory conferences, such as SODA and ICALP, as well as game theory conferences, such as EC and WINE. His work on revenue-optimal auctions was honored with a best paper and best student paper awards in the 14th ACM Conference on Electronic Commerce.
John Wright did his undergraduate education at the University of Texas at Austin and is now is a Ph.D. student at Carnegie Mellon University. His main research areas are hardness of approximation, analysis of Boolean functions, and quantum computing. He has published in STOC, SODA, CCC, APPROX, ITCS and ICALP. In one of his results with Ryan O’Donnell, he proved the best-known NP-hardness of approximation for the well-studied unique games conjecture. In another result, he and his coauthors showed NP-hardness for a natural approximation variation of the graph isomorphism problem.