Workshops

Fall 2021

Computational Complexity of Statistical Inference Reunion

Dec 12, 2022 to Dec 14, 2022

Return to event »

All talks are listed in Pacific Time. Schedule subject to change.

Monday, December 12th, 2022
8:30 am–8:55 am		Coffee and Check In
8:55 am–9:00 am		Opening Remarks
9:00 am–9:45 am		The Complexity of Learning Generative Models Sitan Chen (UC Berkeley)
9:45 am–10:00 am		Break
10:00 am–10:45 am		A Simple and Sharper Proof of the Hypergraph Moore Bound Jun-Ting Hsieh (Carnegie Mellon University)
10:45 am–11:15 am		Break
11:15 am–12:00 pm		Algorithmic Thresholds for Multi-Species Spin Glasses Brice Huang (MIT)
12:00 pm–2:00 pm		Lunch
2:00 pm–2:45 pm		Statistical Efficiency of Score Matching: The View from Isoperimetry Frederic Koehler (Stanford)
2:45 pm–3:15 pm		Break
3:15 pm–5:00 pm		Visioning Session
5:00 pm–6:00 pm		Light Reception

Tuesday, December 13th, 2022
8:30 am–9:00 am		Coffee and Check In
9:00 am–9:45 am		Is It Easier to Count Communities Than Find Them? Fiona Skerman (Uppsala University, Sweden)
9:45 am–10:00 am		Break
10:00 am–10:45 am		Optimality of AMP Among Low-Degree Polynomials Alex Wein (UC Davis)
10:45 am–11:15 am		Break
11:15 am–12:00 pm		Nearly Optimal Algorithms for Semirandom Planted Clique Pravesh Kothari (Carnegie Mellon University)
12:00 pm–2:00 pm		Lunch
2:00 pm–2:45 pm		Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs Chenghao Guo (MIT)
2:45 pm–3:15 pm		Break
3:15 pm–4:00 pm		Sudakov-Fernique Post-amp, and a New Proof of the Local Convexity of the Tap Free Energy Michael Celentano (UC Berkeley)
4:15 pm–5:00 pm		Differential Privacy Versus Robustness: Black-Box Reductions and Efficient Algorithms Sam Hopkins (MIT)

Wednesday, December 14th, 2022
8:30 am–9:00 am		Break
9:00 am–9:45 am		Statistical-computational Tradeoffs in Tensor Learning Anru Zhang (Duke University)
9:45 am–10:00 am		Break
10:00 am–10:45 am		Polynomial-Time Power-Sum Decomposition of Polynomials Jeff Xu (CMU)
10:45 am–11:15 am		Break
11:15 am–12:00 pm		Nearly Solving Intractable Problems via Mean-Field Convergence: Two Examples Dheeraj Nagaraj (Google Research)
12:00 pm–2:00 pm		Lunch
2:00 pm–2:45 pm		Quantum Algorithms with Shallow Depth Probabilistic Properties and Algorithmic Barriers David Gamarnik (MIT)
2:45 pm–5:00 pm		Social Acitivity