Algorithms and Geometry Collaboration: Principal Investigators
Alexandr Andoni is an associate professor at Columbia University and a member of Columbia’s Data Science Institute. He graduated from Massachusetts Institute of Technology in 2009, with a Ph.D. thesis on nearest neighbor search in high-dimensional spaces. Following graduation, he was a postdoctoral researcher at the Center for Computational Intractability, hosted by Princeton, New York University and the Institute for Advanced Study. Andoni then joined Microsoft Research Silicon Valley, where he was a full-time researcher until 2014. Afterward, he was a visiting scientist at the Simons Institute for the Theory of Computing at the University of California, Berkeley, until joining Columbia in 2015.
Andoni is a theoretical computer scientist with a general research focus on advancing algorithmic foundations of massive data. His concrete interests revolve around high-dimensional geometry, metric embeddings, sublinear (space and time) algorithms, theoretical machine learning and the connections among these areas.
Sanjeev Arora is Charles C. Fitzmorris Professor of Computer Science at Princeton University. Arora earned his Ph.D. in Computer Science at the University of California, Berkeley in 1994. He has received the ACM SIGACT-EATCS Gödel Prize (2001 and 2010), Packard Fellowship for Science and Engineering (1997), ACM-Infosys Foundation Award in the Computing Sciences (2012), Fulkerson Prize (2012) and Simons Investigator Award in Computer Science (2012). He served as the founding director for the Center for Computational Intractability at Princeton.
His research spans several areas of theoretical computer science, including computational complexity, approximation algorithms, geometric embeddings of metric spaces, and high-dimensional problems in machine learning.
Tim Austin is an assistant professor at New York University’s Courant Institute of Mathematical Sciences. He completed his Ph.D. at University of California, Los Angeles in 2010 and is now a Clay Research Fellow for the period 2010–2015.
He is a pure mathematician working in analysis, probability and ergodic theory. He has spent some years primarily on the ergodic theoretic phenomenon of multiple recurrence, which has a close interaction with additive combinatorics, but he has also developed interests in metric spaces and in probability on large discrete structures. His more recent work focuses on properties of certain finite metric spaces that emerge from the study of stationary stochastic processes, capturing various important features of these processes, such as their entropy.
Mark Braverman is an assistant professor of computer science at Princeton University, where he has been on the faculty since 2011. He received his Ph.D. in 2008 from the University of Toronto under the supervision of Stephen Cook. Prior to joining Princeton, Braverman spent two years as a postdoc at Microsoft Research New England and a year as a faculty member at the University of Toronto. He is a recipient of the Alfred P. Sloan Research Fellowship, NSF CAREER Award, Turing Centenary Research Fellowship, and Packard Fellowship in Science and Engineering.
His interests include complexity theory, information theory, algorithms, the theory of computation in dynamical systems, and applications of computer science and game theory in healthcare and medicine. Braverman’s recent work developed and expanded the connections between information theory and computational complexity, by extending the reach of Shannon’s information theory to interactive computation.
Jeff Cheeger is a Silver Professor of Mathematics at the Courant Institute of Mathematical Sciences, New York University. He is a member of the National Academy of Sciences (1997) and American Academy of Arts and Sciences (2006), a fellow of the American Mathematical Society (2013) and a foreign member of the Finnish Academy of Science and Letters (1998). He was awarded the 14th Veblen Prize in Geometry (2001).
His research interests include differential geometry, geometric analysis and its connections with topology, as well as analysis on metric measure spaces and its connections with bi-Lipschitz embeddings.
Subhash Khot is a professor of computer science at the Courant Institute of Mathematical Sciences, New York University. Prior to joining NYU, he was on the faculty of Georgia Institute of Technology during 2004–2007. He has a Ph.D. from Princeton University in 2003. Khot received the Microsoft Research New Faculty Fellowship Award in 2005 and the Alan T. Waterman Award in 2010 for outstanding contribution towards computational complexity in unique games conjecture. In 2014, he was awarded the Rolf Nevanlinna Prize from the International Mathematical Union for his work on unique games conjecture.
Khot’s research is centered on computational complexity and its connections to geometry and analysis. In particular, he is interested in investigating whether one can efficiently compute approximate solutions to the so-called NP-hard problems for which efficiently computing exact solutions is widely believed to be infeasible.
Bruce Kleiner is a professor of mathematics at the Courant Institute of Mathematical Sciences at New York University. Kleiner received his Ph.D. in mathematics from the University of California, Berkeley in 1990. He received the National Academy of Sciences Award for scientific reviewing of Grigori Perelman’s solution of the Poincaré Conjecture in 2013.
His research interests are in geometric analysis, geometric group theory and geometric topology. These areas involve a mixture of ideas from geometry, analysis, topology and algebra. Current research topics include: geometric evolution equations, such as the Ricci flow and mean curvature flow; quasi-isometric rigidity; quasisymmetric structure of self-similar spaces, such as boundaries of hyperbolic groups; bi-Lipschitz embedding problems; and analysis on singular spaces, such as Carnot groups, and spaces satisfying Poincare inequalities.
Assaf Naor is a professor of mathematics at Princeton University. He received his Ph.D. in 2002 from Hebrew University of Jerusalem, working under the supervision of Joram Lindenstrauss. Prior to joining the faculty of Princeton University in 2014, Naor was a Professor at the Courant Institute of Mathematical Sciences of New York University. Before joining NYU, he was a Theory Group researcher for Microsoft Research Redmond.
Naor is an editor of Journal of the American Mathematical Society, Journal of Topology and Analysis, Theory of Computing, International Mathematics Research Notices, Probability Theory and Related Fields and Mathematika, and he serves on the scientific advisory boards of the Institute for Pure and Applied Mathematics (IPAM), the Fields Institute for Research in Mathematical Sciences, and the American Institute of Mathematics (AIM).
He conducts research on the interface of analysis and geometry, with emphasis on discovering new structural aspects of metric spaces and harnessing this information for various applications, ranging from functional analysis to harmonic analysis, probability theory, group theory, complexity theory and approximation algorithm.
Ran Raz is a professor of theoretical computer science at the Weizmann Institute of Science, Israel. Currently, he is also a five-year visiting professor at the Institute for Advanced Study, Princeton. Ran received his B.Sc. in mathematics and physics (1987) and Ph.D. in mathematics (1992) from Hebrew University of Jerusalem. After spending two years as a postdoc at Princeton University, he joined the Weizmann Institute of Science in 1994. Ran was a visiting professor at the Institute for Advanced Study (2000–2001, 2002) and a visiting professor at Microsoft Research Redmond (2006) and Microsoft Research New England (2009).
Raz’s main research area is complexity theory, with a focus on proving lower bounds for computational models. More specifically, he is interested in Boolean and arithmetic circuit complexity, communication complexity, probabilistically checkable proofs, quantum computation and communication, and randomness and derandomization.
Oded Regev is a professor in the Courant Institute of Mathematical Sciences of New York University. Prior to joining NYU, he was affiliated with Tel Aviv University and the École Normale Supérieure, Paris under the French National Centre for Scientific Research (CNRS). He received his Ph.D. in computer science from Tel Aviv University in 2001. He is the recipient of the Wolf Foundation’s Krill Prize for Excellence in Scientific Research in 2005, as well as best paper awards in STOC 2003 and Eurocrypt 2006. He was awarded a European Research Council (ERC) Starting Grant in 2008.
His main research areas include theoretical computer science, cryptography, quantum computation and complexity theory. A main focus of his research is in the area of lattice-based cryptography, where he introduced several key concepts, including the ‘learning with error’ problem and the use of Gaussian measures.
Michael Saks is a distinguished professor of mathematics at Rutgers University. He received his Ph.D. in applied mathematics from the Massachusetts Institute of Technology, and has held positions at the University of California, Los Angeles, Bell Communications Research, University of California, San Diego, and Microsoft Research. He is a past winner of the Gödel Prize from the ACM SIGACT and EATCS.
Amit Singer is a professor of mathematics and a member of the executive committee of the Program in Applied and Computational Mathematics (PACM) at Princeton University. He joined Princeton as an assistant professor in 2008. From 2005 to 2008 he was a Gibbs Assistant Professor in Applied Mathematics at the Department of Mathematics, Yale University.
Singer received his B.Sc. degree in Physics and Mathematics and his Ph.D. degree in applied mathematics from Tel Aviv University, Israel, in 1997 and 2005, respectively. He was awarded the Moore Investigator in Data-Driven Discovery Award (2014), the Simons Investigator Award (2012), the Presidential Early Career Award for Scientists and Engineers (2010), the Alfred P. Sloan Research Fellowship (2010) and the Haim Nessyahu Prize in Mathematics (2007). His current research in applied mathematics focuses on theoretical and computational aspects of data science, and on developing computational methods for structural biology.
David Steurer is an assistant professor in the department of computer science at Cornell University. Steurer received his Ph.D. from Princeton University and was a postdoctoral researcher at Microsoft Research New England for two years before joining Cornell University. He is the recipient of the 2010 FOCS Best Paper Award, the 2011 ACM Doctoral Dissertation Award Honorable Mention, an NSF CAREER Award and an Alfred P. Sloan Research Fellowship.
He investigates the power and limitations of efficient algorithms for optimization problems that are at the heart of computer science and its applications. A focus of his work has been the unique games conjectures whose resolution — no matter in which direction — promises new insights into the capabilities of efficient algorithms. As part of an approach to resolve this conjecture, Steurer studies provable guarantees of the sum-of-squares method, a compelling meta-algorithm that applies to a wide-range of problems and has the potential to unify the design of efficient algorithms for difficult optimization problems.