Algorithms, complexity, and optimization.
Geometry and analysis at the interface between the continuous and discrete.
Probability and stochastic processes.
- University of California at Berkeley
Ph.D., Computer Science, May 2005
Advisor: Christos H. Papadimitriou
Thesis: Metric geometry, geometric algorithms, and combinatorial optimization
- Purdue University, West Lafayette, Indiana
B.S. (Honors), Mathematics & Computer Science (1997—2001)
Honors and awards
- Scientific Advisory Board, Simons Institute for Theoretical Computer Science, 2017—present
- Editor, Forum of Mathematics Sigma and Pi (TCS cluster), 2017—present
- Associate editor, SIAM Journal on Computing, 2015—present
- Associate editor, SIAM Journal on Discrete Mathematics, 2015—2017
- Guest editor, SIAM Journal on Computing, special issue for papers from FOCS 2007
- Conference and workshop organization:
- Co-organizer, FOCS 2018 Workshop Day
- Co-organizer, FOCS 2017 Workshop Day
- Co-organizer, workshop on "Algebraic and spectral graph theory" at the
Banff International Research Institute. July 31—August 5, 2016
- Co-organizer, UW-MSR Summer Institute on "Learning, optimization, and stochastic processes." Alderbook,
WA. August 23—26, 2015
- Co-organizer and chair, semester program on "Algorithmic Spectral Graph Theory" at the
Simons Institute for the Theory of Computing, Berkeley, CA, Fall 2014
- Co-organizer of the workshop "Spectral algorithms: From theory to practice" at the Simons
Institute for the Theory of Computing, Berkeley, CA, October 27—31, 2015
- Organizer of the invited workshop "$L_1$ embeddings and flow-cut gaps" at the ACM Symposium
on Computational Geometry, 2012
- Co-organizer, semester program on "Metric geometry, algorithms, and groups" at the Centre Emile Borel
(Institute Henri Poincaré), Paris, France, Winter 2011
- Program committees:
- APPROX 2018: 21st Workshop on Approximation Algorithms for Combinatorial Optimization
- STOC 2017: 49th Annual Symposium on the Theory of Computing
- FOCS 2014: 55th Annual Symposium on the Foundations of Computer Science
- ICALP 2014: 41st Annual International Colloquium on Automata and Complexity
- SODA 2014: 25th Annual ACM-SIAM Symposium on Discrete Algorithms
- ISAAC 2013: 24th International Symposium on Algorithms and Computation
- ESA 2011: 19th Annual European Symposium on Algorithms
- FOCS 2010: 51st Annual Symposium on Foundations of Computer Science
- COCOON 2010: 16th Annual International Computing and Combinatorics Conference
- SODA 2009: 20th Annual ACM-SIAM Symposium on Discrete Algorithms
- FOCS 2007: 48th Annual Symposium on Foundations of Computer Science
- APPROX 2006: 9th Workshop on Approximation Algorithms for Combinatorial Optimization
- Summer school organization and lectures:
- Invited lectures on "Semidefinite extended formulations and sums of squares"
at the Summer School on Combinatorial Optimization, Hausdorff Institute for Mathematics,
Bonn, Germany. September, 2015.
- Co-organizer of the "Experience Theory Project" for advanced graduate students. Hosted
at UW and Microsoft Research, Summer, 2012
- Co-organizer of the "Experience Theory Project" for talented undergraduates. Hosted
at UW and Microsoft Research, Summer, 2010
- Co-organizer of a summer school on "Analysis and geometry in the theory of computing" at Indiana
University, Summer 2009
- NSF CCF-1616297
Entropy maximization in approximation, learning, and complexity.
Sep, 2016—Aug, 2019.
- NSF CCF-1407779
On the power of mathematical programming in combinatorial optimization.
Jul, 2014—May 2018.
- NSF CCF-1217256
Metric geometry for combinatorial problems. Aug, 2012—Jul, 2015.
- NSF CCF-0915251
Spectral analysis, spectral algorithms, and beyond.
Sep, 2009—Aug, 2012.
- NSF CCF-0644037
Geometric phenomena in algorithms and complexity. Feb, 2007—May 2011.
- BSF #2006052
Some complexity issues between P and NP. Jun, 2007—Jun, 2010.
- Ph.D. students
- Jeffrey Hon, 2016—present
- Mohammad Moharrami, 2008—2013
- Alexander B. Jaffe, 2007—2013
- Punyashloka Biswal, 2007—2011 (left with Masters)
- Visiting graduate students
- Andrea Francke (ETH Zurich)
- Teng Qin (ENS Paris)
- Austin Stromme, 2015—2018
- Jaden Stock, 2017
- Yueqi Sheng, 2015—2016
- Ben Eggers, 2014—2016
- Arnaud de Mesmay, 2011
- Will Johnson, 2010
- Justin Vincent, 2006
- Ronen Eldan, Aug—Mar, 2015.
- Tsz Chiu Kwok, Aug—Dec, 2014.
- Jian Ding, Sep—Dec, 2011.
- Ph.D. exam committees
- Shirshendu Ganguly (Math)
- David J. Rosenbaum
- Elizabeth Crosson (Physics)
- Matthew Scott Junge (Math)
- Joel W. Barnes (Math)
- Stephen D. Lewis (Math)
- Dang-Trinh Huynh-Ngoc
- Michael Goff (Math)
Long-term invited visits
- Program member, Simons Institute for the Theory of Computing, October—November, 2017.
- Program organizer, Simons Institute for the Theory of Computing, August—December, 2014.
- Visiting Scholar, U. C. Berkeley, September 2012—August, 2013.
- Visiting Professor, Institute Henri Poincaré, Paris, France, January—March, 2011.
- Institute for Pure and Applied Mathematics, Los Angeles, California, January—February, 2008.
- Massachusetts Institute of Technology, August—September, 2007.
- Université Paris-Sud 11, Orsay, France, June—July, 2007.
- Hebrew University, Jerusalem, December—January, 2006.
- Plenary Speaker, 20th Annual Conference on Quantum Information Processing.
Seattle, WA, Jan, 2017.
- Plenary Lecture Series, Workshop on Positive Semidefinite Rank.
Institute for Mathematical Sciences, Singapore, Feb, 2016.
- Bernoulli Lecture. EPFL, Dec, 2015.
- Plenary Lecture, Workshop on Relaxations and Polyhedral Methods.
University of Bonn, Nov, 2015.
- Charles River Lectures on Probability and Related Topics.
Harvard and Microsoft Research, Oct, 2015.
- Avner Magen Memorial Lecture. Fields Institute, Toronto, May, 2015.
- Keynote Lectures, Topics in Differential Geometry and its Discretizations.
Tohoku University, Jan, 2015.
- Open Lecture. Simons Institute for the Theory of Computing, Dec, 2014.
- Other recent lectures:
- Workshop on Optimization, Complexity, and Invariant Theory, IAS, Princeton, Jun, 2018
- Conference on high-dimensional combinatorics, IIAS, Jerusalem, Apr, 2018
- Theory seminar, UC Berkeley, Apr, 2018
- Workshop on Approximation algorithms and Hardness of Approximation, Banff, CA, Nov, 2017
- Workshop on Hierarchies, Extended formulations, and Matrix-analytic techniques, Simons Institute, Nov, 2017
- Elegance in Probability—Conference in honor of Russ Lyons’ 60th, Tel Aviv, Sep, 2017
- Workshop on Proof Complexity and Beyond, Oberwolfach, Aug 2017
- Bellairs workshop on Data, Learning, and Optimization, Barbados, Apr, 2017
- Math colloquium, University of Chicago, Mar 2017
- CS Theory seminar, University of Chicago, Mar 2017
- Rainwater seminar, University of Washington, Jan 2017
- Probability seminar, UBC, October, 2016
- Conference on the Mathematics of Jiří Matoušek, Prague, July, 2016.
- Theory seminar, Caltech, May, 2016.
- Simons Workshop on Analysis of Boolean Functions, Bavaria, Germany, Apr, 2016.
- Probability seminar, University of Washington, Mar 2016.
- Data Science & Society seminar, University of Washington, Mar, 2016.
- Workshop on Counting Complexity and Phase Transitions, Simons Institute, Berkeley, CA, Feb, 2016.
- Workshop on Convexity, Probability, and Discrete Structures, University Paris-Est Marne-La-Vallée, Oct, 2015.
- Workshop on Graphs, Groups, and Stochastic Processes, BIRS, Banff, CA, Jun, 2015.
- Probability seminar, Stanford University, May, 2015
- Bellairs Workshop on Combinatorial Optimization, Barbados, Apr, 2015.
- Workshop on the Power of Randomness in Computation, Georgia Tech, Mar, 2015.
- Limitations of Convex Programming: Extended formulatins and PSD rank, Dagstuhl, Germany, Feb, 2015.
- Probability seminar, University of Chicago, Feb, 2015.
- Theory of Computation seminar, University of Chicago, Feb, 2015.
- Real Analysis Reunion Workshop, Simons Institute, Berkeley, CA, Dec, 2014.
- Workshop on Fast Algorithms via Spectral Methods, Simons Institute, Berkeley, CA, Nov, 2014.
- Combinatorics seminar, University of Bristol, UK, Nov, 2014.
- Workshop on Combinatorial Optimization, Oberwolfach, Germany, Nov, 2014.
- Discrete Mathematics seminar, Institute for Advanced Study, Princeton, Nov, 2014.
- Industry Day, Simons Institute, Berkeley, CA, Nov, 2014.
- Probability seminar, UC Berkeley, Oct, 2014.
- Theory lunch, UC Berkeley, Oct, 2014.
- Combinatorics seminar, UC Berkeley, Sep, 2014.
- Algorithms seminar, École Normale Supérieure, Paris, Sep, 2014.
- 5th Cargèse Workshop on Combinatorial Optimization, Cargese, France, Sep, 2014.
- Workshop on Approximation and Hardness of Approximation, BIRS, Banff, CA, Aug, 2014.
- Workshop on Graphs, Groups, and Stochastic Processes, Renyi Institute, Budapest, Jun, 2014.