Workshops

Fall 2020

Computational Phase Transitions

Sep 21, 2020 to Sep 25, 2020

Return to event »

This workshop is being live streamed on our website. Full participation (including the capacity to ask questions) will be available via Zoom webinar.

All talk times are in Pacific Time.

Monday, September 21st, 2020
9:00 am–9:15 am		Opening Remarks
9:15 am–9:40 am		Counting Solutions to Random CNF Formulas Leslie Ann Goldberg, University of Oxford
9:40 am–9:55 am		Break
9:55 am–10:20 am		Testing Correlation of Unlabeled Random Graphs Jiaming Xu, Duke University
10:20 am–10:35 am		Break
10:35 am–11:00 am		Local Statistics, Semidefinite Programming, and Community Detection Jess Banks, UC Berkeley
11:05 am–11:30 am		Local Statistics, Semidefinite Programming, and Community Detection II Sidhanth Mohanty, UC Berkeley
11:30 am–11:45 am		Break
11:45 am–12:45 pm		Incremental Approximate Message Passing Ahmed El Alaoui, Stanford University
2:00 pm–3:00 pm		Social Hour

Tuesday, September 22nd, 2020
9:10 am–9:15 am		Introductions
9:15 am–9:40 am		Equitable Colorings Afonso Bandeira, NYU
9:40 am–9:55 am		Break
9:55 am–10:20 am		A Positivity-First Approach to Sum-of-Squares Over the Hypercube Tim Kunisky, NYU
10:20 am–10:35 am		Break
10:35 am–11:00 am		Phase Retrieval in High Dimensions: Statistical and Computational Phase Transitions Florent Krzakala, ENS
11:00 am–11:15 am		Break
11:15 am–12:15 pm		Open Problems Session
2:00 pm–3:00 pm		Social Hour

Wednesday, September 23rd, 2020
8:55 am–9:00 am		Introductions
9:00 am–9:25 am		Optimization of Full-RSB Spherical Spin Glasses Eliran Subag, Courant
9:25 am–9:40 am		Break
9:40 am–10:05 am		Thresholds of Descending Algorithms in Inference Problems Stefano Sarao Mannelli, IPhT CEA-Saclay
10:05 am–10:20 am		Break
10:20 am–10:45 am		The Sum-of-Squares Approach to Clustering Non-Spherical Gaussian Mixtures Pravesh Kothari, CMU
10:45 am–11:00 am		Break
11:00 am–11:25 am		Information/Computation Gaps in Heavy-Tailed Statistics Sam Hopkins, UC Berkeley
11:25 am–11:40 am		Break
11:40 am–12:40 pm		Pedagogical Talk: Random Optimisation Problems Amin Coja-Oghlan, Goethe University
2:00 pm–3:00 pm		Social Hour

Thursday, September 24th, 2020
9:10 am–9:15 am		Introductions
9:15 am–9:40 am		Correlation Decay for Hard Spheres via Markov Chains Samantha Petti, Harvard
9:40 am–9:55 am		Break
9:55 am–10:20 am		Sampling From the Random Cluster Model at All Temperatures on Random Graphs Will Perkins, University of Illinois at Chicago
10:20 am–10:35 am		Break
10:35 am–11:00 am		The Rank of Sparse Random Matrices Jane Gao, University of Waterloo
11:00 am–11:15 am		Break
11:15 am–12:15 pm		Pedagogical Talk: Failure of Low-Degree Polynomials Alex Wein, NYU
2:00 pm–3:00 pm		Social Hour

Friday, September 25th, 2020
9:10 am–9:15 am		Introductions
9:15 am–9:40 am		The Overlap Gap Property in Principal Submatrix Recovery Subhabrata Sen, Harvard
9:40 am–9:55 am		Break
9:55 am–10:20 am		Free Energy Wells and Overlap Gap Property in Sparse PCA Ilias Zadik, NYU
10:20 am–10:35 am		Break
10:35 am–11:00 am		Reducibility and Statistical-Computational Gaps from Secret Leakage Guy Bresler, MIT
11:00 am–11:15 am		Break
11:15 am–12:15 pm		Pedagogical Talk: Frameworks for Information-Computation Tradeoffs Tselil Schramm, Stanford University
2:00 pm–3:00 pm		Social Hour