(10 minutes) A quick intro to the low-degree polynomial framework for detection, recovery, and optimization
Bernoulli-IMS One World Symposium, Aug. 2020
[video] [slides]
Mini-course on random tensor models and related topics
Université Paul Sabatier, Toulouse, Oct. 2024
Part I: Intro and Motivation [notes]
Part II: Tensor Networks [notes]
Part III: Tensor PCA [notes]
Part IV: Kikuchi Matrices [notes]
Part V: Tensor Decomposition [notes]
Lecture series on the low-degree polynomial framework
Simons Institute, Berkeley, Fall 2020
(1 hour) Part I: overview, detection, planted clique [video]
(1 hour) Part II: more on detection, sparse PCA [video]
(1 hour) Part III: recovery [video]
(1 hour) Part IV: random optimization problems [video]
(50 minutes) Optimality of AMP Among Low-Degree Polynomials
Banff International Research Station, Aug. 2024
[video] [slides] [paper]
(40 minutes) Fine-Grained Extensions of the Low-Degree Testing Framework
Banff International Research Station, Feb. 2024
[video] [slides] [paper1] [paper2]
(45 minutes) New Techniques for Low-Degree Lower Bounds
FODSI Workshop on Computational Complexity of Statistical Problems, MIT, June 2023
[video] [slides]
(50 minutes) Is Planted Coloring Easier than Planted Clique?
GRAMSIA Workshop, Harvard, May 2023
[video] [slides] [paper]
(1 hour) Average-Case Computational Complexity of Tensor Decomposition
Institute for Advanced Study, Oct. 2022
[video] [slides] [paper]
(50 minutes) Optimal Spectral Recovery of a Planted Vector in a Subspace
One World MINDS Seminar, Aug. 2021
[video] [paper]
(35 minutes) The Kikuchi Hierarchy and Tensor PCA
IPAM Workshop on Mathematical Foundations and Algorithms for Tensor Computations, May 2021
[video] [slides] [paper]
(20 minutes) Counterexamples to the Low-Degree Conjecture
ITCS 2021
[video] [slides] [paper]
(45 minutes) Low-Degree Hardness of Random Optimization Problems
Simons Institute Workshop on Learning and Testing in High Dimensions, Dec. 2020
[video] [slides] [paper1] [paper2]
(50 minutes) Computational Barriers to Estimation from Low-Degree Polynomials
Stanford ISL Colloquium, Oct. 2020
[video] [slides] [paper]
(40 minutes) Subexponential-Time Algorithms for Sparse PCA
MIT MIFODS Workshop on Learning under Complex Structure, Jan. 2020
[video] [slides] [paper]