Tutorials

• How do Transformers Work?, with Daniel Hsu

  Simons Institute Bootcamp, September 2024
  Part 1: Language Models and Attention (video)
  Part 2: Induction Heads and Chain-of-Thought (video)

• Algorithmic Aspects of Reinforcement Learning

  ITA+ALT Tutorial, February 2024
  Part 1: Partial Observability
  Part 2: Function Approximation

• Learning from Dynamics

  ITA Plenary Talk, February 2024
  AMS John von Neumann Lecture, January 2024

• The Method of Moments in Computer Science and Beyond

  Swedish Summer School in Computer Science, July 2022
  Part 1: Tensor Decompositions and Their Applications
  Part 2: Gaussian Mixture Models
  Part 3: Algorithmic Robust Statistics
  Part 4: Inverse Problems in the Sciences

• Rethinking Robustness: From Classification to Contextual Bandits

  UAI Keynote Talk, July 2021

• Tensor Methods in Data Science

  IPAM Tutorial, March 2021
  Part 1: Tensor Decompositions and Their Applications
  Part 2: Tensor Completion and Refuting Random CSPs

• Recent Progress in High-Dimensional Learning

  Simons Institute Tutorial, August 2020
  Part 1: Tensor Decompositions and Their Applications
  Part 2: Robust Estimation in Parameter Learning
  Part 3: Supervised Learning with Massart Noise
  Part 4: Provable Algorithms for Inverse Problems in Physics?

• Sum-of-Squares, with a View Towards Average-case Complexity

  Kavli Institute Tutorial, January 2019

• Sum-of-Squares Proofs, with Pablo Parrilo

  Simons Institute Tutorial, August 2017

• Robustness Meets Algorithms (and Vice-Versa)

  NUS Distinguished Lecture, January 2019
  HALG 2018 Invited Survey, June 2018
  ICML 2017 Invited Tutorial, August 2017

• Algorithmic Aspects of Inference

  IHP Special Program Tutorial, January 2016

• Tensor Decompositions and Their Applications

  Learning at Scale (MADALGO), August 2014

• Extended Formulations and Information Complexity

  Dagstuhl Tutorial, March 2014

• Polynomial Methods in Learning and Statistics

  UAI 2013 Tutorial, July 2013
  Institute for Advanced Study Members' Seminar, March 2012

Advice

• How to do Theoretical Research

  TCS-For-All Talk, October 2024
  Learning Theory Alliance Mentoring Workshop, June 2024

Talks

• Learning from Dynamics

  IFML/Simons Symposium, November 2024
  UC Davis Data Science Seminar, November 2024
  Google Research, October 2024
  MIT LIDS/TOC Colloquium, December 2023
  Harvard CS Theory Seminar, October 2023
  Institute for Advanced Study CSDM Seminar, October 2023
  Harvard Big Data Conference, August 2023

• Reinforcement Learning without Intractable Oracles?

  CSAIL Computing the Future, June 2023
  ONR Program Review, April 2023
  Princeton Machine Learning Seminar, June 2022

• Algorithmic Foundations for the Diffraction Limit

  Institute for Advanced Study CSDM Seminar, October 2023
  One World Mathematics of Information, Data, and Signals, February 2022
  Georgia Tech ARC Colloquium, April 2021
  UT Austin Machine Learning Lab Inaugural Lecture, November 2020

• Learning with Massart Noise, and Connections to Fairness

  Boston University Algorithms and Theory Seminar, 2022
  USC Probability and Statistics Seminar, October 2021
  Princeton ORFE Colloquium, September 2021
  Northwestern Quarterly Theory Workshop, June 2020
  CSAIL-MSR Trustworthy and Robust AI Workshop, June 2020

• Robustly Recovering a Signal, Under a Group Action

  Stanford Theory Seminar, October 2019
  ONR Program Review, October 2019

• Learning Gaussian Graphical Models without Condition Number Bounds

  FODSI Kickoff Workshop, November 2020
  ICERM Workshop on Data Science, May 2019
  Oberwolfach Workshop on High-Dimensional Statistics, May 2019

• Learning Restricted Boltzmann Machines

  Institute for Mathematics and Applications, September 2020
  UT Austin Theory Seminar, March 2019
  MIT MIFODS Workshop, January 2019

• The Paulsen Problem Made Simple

  ICERM Workshop on Computational Algebra, May 2019

• Approximate Counting and the Lovasz Local Lemma

  Santa Fe Institute Workshop, July 2023
  Harvard Probability and Random Matrix Theory Seminar, December 2017
  Princeton Theory Lunch, December 2017
  TTI CS Colloquium, October 2017
  STOC 2017, June 2017
  Institute for Advanced Study CSDM Seminar, March 2017

• Robustness Meets Algorithms

  UPenn Theory Seminar, November 2019
  Stanford Statistics Seminar, October 2019
  MIT Applied Math Colloquium, September 2018
  SWAT Invited Talk, June 2018
  Princeton Center for Theoretical Science Workshop, May 2018
  NYU Math and Data Seminar, April 2018
  Simons Math+X Symposium at Rice, January 2018
  JASON Fall Meeting, November 2017
  Yale Statistics Seminar, October 2017
  Summer Research Institute at EPFL, June 2017
  Northeastern Theory Seminar, April 2017
  MIT Stochastics and Statistics Seminar, March 2017
  Simons Institute, November 2016
  Southern California Theory Day, November 2016
  Georgia Tech ARC Colloquium, October 2016

• Planted Clique, Sum-of-Squares and Pseudo-Calibration

  Institute for Mathematics and Applications, May 2016
  Simons Institute, May 2016

• How Robust are Thresholds for Community Detection?

  International Bayes Club Seminar, March 2021
  CSAIL-MSR Trustworthy and Robust AI Workshop, January 2019
  MIT MIFODS Workshop, June 2018
  Northwestern Quarterly Theory Workshop, May 2017
  MIT Statistics and Data Science Day, April 2017

• Beyond Matrix Completion

  Princeton PACM Colloquium, March 2016
  FSTTCS 2015 Invited Talk, December 2015
  Harvard Big Data Conference, August 2015
  European Meeting of Statisticians, July 2015
  New England Machine Learning Day, May 2015
  MIT Stochastics and Statistics Seminar, April 2015
  NYU Theory Seminar, April 2015
  Harvard Probability and Random Matrix Theory Seminar, March 2015
  University of Chicago Theory Seminar, March 2015

• Simple, Efficient and Neural Algorithms for Sparse Coding

  Simons Institute, March 2015
  ITA 2015, February 2015
  Workshop on Algorithmic Challenges in Machine Learning (UCSD), January 2015
  Symposium on Learning, Algorithms and Complexity (IISc), January 2015
  Workshop on Learning Theory (FOCM), December 2014

• Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices

  BIRS Workshop on Analytic Techniques in TCS, August 2018
  STOC 2015, June 2015
  MSR/MIT Reading Group, November 2014
  Workshop on Sparse Fourier Transform (FOCS), October 2014

• New Algorithms for Dictionary Learning

  Learning at Scale (MADALGO), August 2014
  Curves and Surfaces, July 2014
  Mathematical Foundations of Learning Theory, July 2014
  COLT 2014, July 2014
  Workshop on Overcoming Intractability in Unsupervised Learning (STOC), May 2014

• A Polynomial Time Algorithm for Lossy Population Recovery

  Simons Institute, September 2014
  Duke Algorithms Seminar, August 2014
  ICERM Workshop on Spectral Methods, May 2014
  ITA 2014, February 2014
  FOCS 2013, October 2013
  TCS+ Seminar, September 2013 (video)
  Princeton Discrete Math Seminar, April 2013
  Princeton Theory Lunch, April 2013

• An Information Complexity Approach to Extended Formulations

  Simons Institute, April 2015
  MIT TOC Colloquium, September 2013
  STOC 2012, June 2013
  NYC Theory Day, May 2013
  Columbia Discrete Math Seminar, April 2013
  ARC Theory Day, April 2013
  Center for Computational Intractability Meeting, December 2012

• New Algorithms for Nonnegative Matrix Factorization and Beyond

  Harvard CS Colloquium, October 2014
  Learning at Scale (MADALGO), August 2014
  UW CS Colloquium, November 2013
  UT Austin CS Colloquium, April 2013
  UCSD CS Colloquium, April 2013
  Carnegie Mellon CS/MLD Colloquium, March 2013
  Cornell CS Colloquium, March 2013
  Princeton CS/PACM Colloquium, March 2013
  MIT Applied Math Special Seminar, February 2013
  Columbia IEOR/CS Colloquium, February 2013
  MSR Silicon Valley Theory Seminar, February 2013
  IBM TJ Watson Theory Seminar, February 2013
  Caltech CMS Colloquium, January 2013
  MSR New England Theory Seminar, January 2013

• An Almost Optimal Algorithm for Computing Nonnegative Rank

  ISSAC 2015 Tutorial, July 2015
  SODA 2013, January 2013

• Learning Topic Models -- Going Beyond SVD

  FOCS 2012, October 2012

• Computing a Nonnegative Matrix Factorization -- Provably

  Cornell Theory Seminar, October 2012
  IBM TJ Watson Theory Lunch, August 2012
  Google Research NYC Theory Seminar, June 2012
  Carnegie Mellon Theory Seminar, December 2011
  University of Texas, Austin Theory Seminar, November 2011

• Finding Structure in Big Data (popular talk)

  Institute for Advanced Study Board of Trustees Meeting, May 2012

• Nearly Complete Graphs Decomposable into Large Induced Matchings

  STOC 2012, May 2012
  Princeton Theory Lunch, April 2012

• Vertex Sparsification: An Introduction, Connections and Applications

  WorKer 2015 Tutorial, June 2015
  Part I: Institute for Advanced Study, November 8th 2011
  Part II: Institute for Advanced Study, November 15th 2011

• Pareto Optimal Solutions for Smoothed Analysts

  Princeton Discrete Math Seminar, March 2012
  Rutgers Discrete Math Seminar, February 2012
  University of California, Berkeley Theory Seminar, September 2011
  Workshop on Beyond Worst Case Analysis (Stanford), September 2011
  STOC 2011, June 2011

• Vertex Sparsification and Oblivious Reductions

  Columbia CS Colloquium, February 2012
  Columbia Discrete Math Seminar, November 2011
  DIMACS Theory Seminar, October 2011
  UCLA CS Colloquium, March 2011
  TTI CS Colloquium, March 2011
  Stanford CS Colloquium, February 2011
  USC CS Colloquium, January 2011
  Georgia Tech ARC Colloquium, January 2011
  Microsoft Research Silicon Valley Theory Seminar, January 2011
  MIT Operations Research Seminar, December 2010
  University of Washington Theory Seminar, December 2010

• Learning Mixtures of Gaussians (video)

  International Workshop on Statistical Learning, June 2013
  UCSD Theory Seminar, April 2013
  Center for Computational Intractability Meeting, September 2011
  Microsoft Research New England Theory Seminar, January 2011
  Institute for Advanced Study CSDM Seminar, January 2011
  Microsoft Research Redmond Theory Lunch, December 2010
  Yale Statistics Seminar, November 2010
  Carnegie Mellon Theory Seminar, September 2010
  Microsoft Research Silicon Valley Theory Seminar, August 2010
  IBM TJ Watson Theory Lunch, May 2010

• Capacitated Metric Labeling

  SODA 2011, January 2011

• Extensions and Limits to Vertex Sparsification

  STOC 2010, June 2010

• Approximation Algorithms for Multicommodity-Type Problems

  Carnegie Mellon Theory Lunch, September 2010
  China Theory Week, September 2010
  Cornell Theory Seminar, February 2010
  Princeton Theory Lunch, December 2009
  University of California, Berkeley Theory Seminar, November 2009
  Stanford Algorithms Seminar, November 2009
  FOCS 2009, October 2009
  MIT Combinatorics Seminar, September 2009
  ATT Research Theory Seminar, May 2009
  Bell Labs Theory Seminar, May 2009

• Some Results on Greedy Embeddings in Metric Spaces

  Microsoft Research Redmond Theory Seminar, March 2009
  FOCS 2008, October 2008