Browse by award year
The Simons Foundation is proud to announce the 2012 grants to graduate students in theoretical computer science with outstanding track records of research accomplishments.
Christopher Beck is a Ph.D. student at Princeton University. He graduated from the California Institute of Technology with a Bachelor of Science with honors in Computer Science and Mathematics. Beck’s work seeks to establish the limits of how efficiently we can solve computational problems. One of his papers studies a popular class of algorithms known as SAT solvers and shows that if their memory is restricted, then they can require exponential running time. Another result concerns how well we can approximately sample from certain distributions when our computation must be small depth, that is, highly parallelizable. Beck and his co-authors showed that even exponentially large bounded depth circuits cannot sample with even exponentially small success from a certain simple distribution.
Zhiyi Huang, a Ph.D. student at the University of Pennsylvania, works in the area of economics and computation. He has published papers in forums such as FOCS, ICALP, RANDOM, SODA and APPROX. His research agenda comprises three main aims: (i) the development of a general method for converting approximation algorithms into truthful mechanisms for social welfare maximization, (ii) characterization and design of computationally efficient and truthful mechanisms that obtain near-optimal revenue for multidimensional problems, and (iii) exploration of connections between mechanism design and differential privacy, aiming to develop mechanisms that are both truthful and differentially private. Huang’s existing publications demonstrate progress on all three aims.
Aleksandar Nikolov is a Ph.D. student in the Department of Computer Science at Rutgers University. He finished his undergraduate studies at St. Peter’s University, New Jersey. His research area is discrepancy theory and its applications. In particular, his work develops new methods for computational aspects of discrepancy theory, and its applications to differential privacy and its extensions. He has published in top conferences of theoretical computer science such as FOCS, STOC, SODA and PODS. For disproving József Beck’s ‘three permutations’ conjecture with Alantha Newman, open since 1984, Joel Spencer awarded them $100 for this solution, and the result will appear in the forthcoming FOCS 2012 conference. With S. Muthukrishnan, he exhibited a connection between the error complexity of differentially private algorithms and combinatorial discrepancy, which leads to new tight upper and lower error bounds for privately computing natural range counting queries. This result was published in STOC 2012. Earlier, with Moses Charikar and Alantha Newman, he proved tight hardness results for approximating discrepancy. Their work exhibited a connection between the hardness of approximating discrepancy and lower bounds for discrepancy. This result appeared in SODA 2011. Alex has also work on extensions of differential privacy, such as pan-privacy, with results that appeared in PODS.
Eric Price is a fourth-year Ph.D. student at MIT researching theoretical aspects of sparse recovery and compressive sensing. He received his bachelor’s degree from MIT in 2009. He is a co-author of several papers, published in conferences such as STOC, FOCS and SODA. One of his algorithms, which Technology Review named one of the top-ten emerging technologies of 2012, computes the discrete Fourier transform faster than the well-known FFT algorithm on sparse data. Another result shows how compressive sensing can significantly benefit from adaptively chosen measurements. A recipient of an NSF graduate research fellowship, he has won gold medals at the International Olympiad in Informatics, International Mathematical Olympiad and ACM International Collegiate Programming Contest.
Vasileios (Vasilis) Syrgkanis
Vasilis Syrgkanis received his undergraduate degree from the National Technical University of Athens, Greece. He is now a Ph.D. student at Cornell University and served as an intern with Microsoft Research at their Cambridge and New England labs for two summers. He is currently working in the area of algorithmic game theory with a special focus on understanding the outcome quality of simple mechanisms for electronic markets. Specifically he works on sequential auction problems, and on the analysis of a variety of games such as congestion games, non-simultaneous-move games, cost-sharing games and resource-allocation games in both the Bayesian and the full information setting. His papers have been published in SODA, ITCS, EC, and WINE.
Yuan Zhou received his bachelor’s degree in Computer Science from Tsinghua University in 2009, where he attended the Special Pilot CS Class supervised by Turing Award laureate Professor Andrew Yao. Zhou is currently a graduate student at Carnegie Mellon University, working on theoretical computer science with Professors Venkatesan Guruswami and Ryan O’Donnell. His research interests focus on approximability of fundamental optimization problems. In his past research projects, he designed approximation algorithms and proved inapproximability results for solving sparse linear equations, graph cut and graph bisection problems, unique games, several constraint satisfaction and ordering problems, and the densest subgraph problem. Zhou also publishes work on other topics of theoretical computer science, including analysis of Boolean functions, algebraic dichotomy theory, algorithmic game theory and quantum information theory.