Simons Investigators

Vinod Vaikuntanathan’s research is in the foundations of cryptography and its applications to theoretical computer science at large. He is known for his work on fully homomorphic encryption, a powerful cryptographic primitive that enables complex computations on encrypted data, as well as lattice-based cryptography, which lays down a new mathematical foundation for cryptography in the post-quantum world. Recently, he has been interested in the interactions of cryptography with quantum computing, as well as with statistics and machine learning.

Santosh Vempala has made fundamental advances in the theory of algorithms: for sampling high-dimensional distributions, computing the volume of a convex body, optimization over convex sets, randomized matrix approximation, as well as basic problems in machine learning. In many cases, these were the first polynomial-time algorithms and co-evolved with insights into high-dimensional geometry and probability. Recent highlights include proving that sufficiently sparse linear systems can be solved faster than matrix multiplication (Ax=b, the workhorse of modern computation); extending sampling methods to non-Euclidean (Riemannian) geometries to make them faster (leading to practical methods in very high dimension); pioneering techniques for algorithmic robust statistics (immune to adversarial corruptions); and developing a rigorous theory of computation and learning in the brain in a biologically plausible model (how does the mind emerge from neurons and synapses?). He continues to be puzzled by whether an unknown polytope can be learned in polytime from samples, whether its diameter is bounded by a polynomial in its description length, whether its volume can be computed in polytime without randomization, and whether the answers to these questions will be discovered by humans or by AI.

Virginia Vassilevska Williams' research is broadly in theoretical computer science, and more specifically in designing algorithms for graphs and matrices, and uncovering formal relationships between seemingly very different computational problems. She is known for her work on fast matrix multiplication, both in co-developing the world's fastest algorithm and in proving limitations on the known techniques for designing matrix multiplication algorithms. Williams is also one of the original founders and leaders of fine-grained complexity, a blossoming new branch of computational complexity.

Shayan Oveis Gharan’s research exploits deep tools from mathematics, such as the theory of real stable and log-concave polynomials, spectral graph theory and high-dimensional simplicial complexes to design and analyze algorithms for discrete objects. He is known for his results on improved approximation algorithms for classical optimization problems such as traveling salesperson problems, as well as his analysis of the mixing time of Markov chains to efficiently sample from complex probability distributions such as the uniform distribution over the bases of a matroid.

Shachar Lovett works broadly in theoretical computer science and related mathematics. He focuses on the study of structure and randomness, and how they are pivotal to our understanding of efficient computation. One facet of Lovett’s work is discovering the mathematical structures that underlie efficient computation, such as combinatorial structure in complexity theory, geometric structure in machine learning and algebraic structure in coding theory. Another facet is understanding the power of randomness in computation. Structure and randomness can be seen as complementary, and Lovett’s work aims to identify the fracture lines between structure and randomness, towards a better understanding of computation.

Gregory Valiant works at the intersection of algorithms, information theory, learning and statistics to understand how to extract as much information as possible from data in various fundamental settings. What information can be inferred if the amount of data is sublinear in the support size or dimensionality of the distribution in question? How do restrictions on the amount of available memory affect the time or amount of data required to learn or optimize? Can we make learning and estimation algorithms robust to outlying training data or settings where the test and training sets are dissimilar?

Maria-Florina Balcan’s research spans machine learning, algorithms and algorithmic game theory. She introduced general techniques that helped put modern machine-learning paradigms on solid theoretical foundations, including learning from limited labeled data, distributed learning, noise-tolerant learning and life-long learning. She also provided fundamental contributions to the area of analysis of algorithms beyond the worst-case, by providing both new models of realistic (non worst-case) instances and general techniques for designing and analyzing algorithms derived in a data driven fashion.

Amit Sahai’s research proposes fundamental new concepts in cryptography and establishes new feasibility results. He is best known for his works proposing the notions of indistinguishability obfuscation and functional encryption, and for his recent work establishing the feasibility of indistinguishability obfuscation and functional encryption for general computations based on well-studied hardness conjectures.

Thomas Vidick’s research is at the interface of theoretical computer science, quantum information and cryptography. He is known for his work in the theory of quantum interactive proofs, including results on device-independent cryptography, certified randomness and the complexity of quantum multiprover interactive proof systems. The study of quantum entanglement provides a unifying goal behind all these areas and a focal point for his current research.

Venkatesan Guruswami's research has led to major advances in the theory of error-correcting codes, approximate optimization, pseudorandomness and related complexity-theoretic and mathematical aspects. His work on list decoding has yielded codes with minimum possible redundancy for correcting worst-case errors. His recent works include notable progress on polar codes, deletion-correcting codes, codes for cloud storage and constraint satisfaction problems.

Omer Reingold is the Rajeev Motwani professor of computer science at Stanford University. His research is in the foundations of computer science and most notably in computational complexity, cryptography and the societal impact of computation. Among his fundamental contributions are a small-memory deterministic graph walks, explicit constructions of lossless expander graphs, randomness extractors and pseudorandom functions, as well as establishing influential notions in the area of algorithmic fairness. He is an ACM Fellow, and among his distinctions are the 2005 Grace Murray Hopper Award and the 2009 Gödel Prize.

David Woodruff works in the foundations of data science, specifically in data streams, machine learning, randomized numerical linear algebra, sketching and sparse recovery. One of his breakthroughs was the first randomized relative error approximation algorithms for least squares regression and low rank approximation that run in input sparsity time (i.e., time proportional to the number of non-zero entries in the input). His work on data streams includes the first optimal algorithms for approximately counting distinct elements, approximating the frequency moments and finding heavy hitters, as well as optimal lower bounds for the complexity of certain algorithms.

David Blei studies probabilistic machine learning, including its theory, algorithms and application. He has made contributions to unsupervised machine learning for text analysis, approximate Bayesian inference with variational methods, flexible modeling with Bayesian nonparametrics and many applications to the sciences and humanities.