Workshops

Fall 2021

Rigorous Evidence for Information-Computation Trade-offs

Sep 13, 2021 to Sep 17, 2021

Return to event »

All talks are listed in Pacific Time. Please note some speakers may present remotely. Schedule subject to change.

Monday, September 13th, 2021
9:20 am–9:30 am		Opening Remarks
9:30 am–10:20 am		Smoothed CSP Refutation Is As Easy As Random, For Both Efficient Algorithms And Certificates Pravesh K. Kothari (Carnegie Mellon University)
10:20 am–10:45 am		Sum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower Bounds Aaron Potechin (University of Chicago)
10:45 am–11:10 am		Break
11:10 am–11:35 am		Planted Geometric Matching Problems Dmitriy (Tim) Kunisky (NYU)
11:35 am–12:00 pm		Robust Parameter Estimation For Random Graphs Jayadev Acharya (Cornell University)
12:00 pm–2:00 pm		Lunch
2:00 pm–2:50 pm		New Techniques For Proving Fine-Grained Average-Case Hardness Andrea Lincoln (UC Berkeley)
2:50 pm–3:15 pm		Charting the Landscape of Memory/Data Tradeoffs in Continuous Optimization: A Survey of Open Problems Gregory Valiant (Stanford University)
3:15 pm–3:40 pm		Break
3:40 pm–4:05 pm		Computational Barriers to Estimation from Low-Degree Polynomials Tselil Schramm (Stanford University)
4:05 pm–4:30 pm		The Overlap Gap Property For Inference: Power And Limitations Ilias Zadik (Massachusetts Institute of Technology)
4:30 pm–5:30 pm		Reception

Tuesday, September 14th, 2021
		Joint Session with EPFL
8:30 am–8:55 am		To Be (Hard) or Not Be: The Spiked Matrix-Tensor Model Florent Krzakala (École polytechnique fédérale de Lausanne)
8:55 am–9:20 am		Are Generative Models The New Sparsity? Bruno Loureiro (EPFL)
9:20 am–9:30 am		Break
9:30 am–10:20 am		A Few Simple Average-Case Reduction Techniques And Their Surprising Effectiveness Guy Bresler (Massachusetts Institute of Technology)
10:20 am–10:50 am		Break
10:50 am–11:15 am		The Initial Search Phase Of Stochastic Gradient Descent For High-Dimensional Inference Tasks Reza Gheissari (UC Berkeley)
11:15 am–11:40 am		Local Convexity Of The Tap Free Energy And Amp Convergence For Z2-Synchronization Song Mei (UC Berkeley)
11:50 am–1:30 pm		Lunch
1:30 pm–1:55 pm		Signal Recovery With Generative Priors Paul Hand (Northeastern University)
1:55 pm–2:20 pm		All-or-Nothing Statistical and Computational Phase Transitions in Sparse Spiked Matrix Estimation Cynthia Rush (Columbia University)

Wednesday, September 15th, 2021
		Joint Session with EPFL
8:30 am–8:55 am		Phase Retrieval In High Dimensions: Statistical And Computational Phase Transitions Antoine Maillard (Ecole Normale Supérieure - Paris)
8:55 am–9:20 am		Mismatched Monte Carlo Algorithms For The Planted Clique Problem Maria Chiara Angelini (Sapienza - Università di Roma)
9:20 am–9:30 am		Break
9:30 am–10:20 am		Putting Quantum Supremacy on a Rigorous Footing Umesh Vazirani (UC Berkeley)
10:20 am–10:50 am		Break
10:50 am–11:40 am		Optimizing Noncommutative Polynomials: The SYK Model Ryan O'Donnell (Carnegie Mellon University)
11:50 am–1:30 pm		Lunch
1:30 pm–1:55 pm		The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials Brice Huang (Massachusetts Institute of Technology)
1:55 pm–2:20 pm		Tight Algorithmic Thresholds for Spin Glass Hamiltonians Mark Sellke (Stanford University)

Thursday, September 16th, 2021
		Joint Session with EPFL
8:30 am–9:20 am		Average-Case Hardness in Proof Complexity Susanna F. de Rezende (Czech Academy of Sciences)
9:20 am–9:30 am		Break
9:30 am–10:20 am		Extractor-Based Approach To Memory-Sample Tradeoffs Sumegha Garg (Harvard University)
10:20 am–10:50 am		Break
10:50 am–11:15 am		Optimal Spectral Recovery Of A Planted Vector In A Subspace Alexander Wein (UC Berkeley)
11:15 am–11:40 am		Refutation and Spectrally Quiet Planting of Cuts and Colorings in Random Graphs Jess Banks (UC Berkeley)
11:50 am–1:30 pm		Lunch
1:30 pm–2:20 pm		Differential Privacy And The Complexity Of Simple Queries Jonathan Ullman (Northeastern University)

Friday, September 17th, 2021
9:30 am–9:55 am		The Estimation Error of General First Order Methods Michael Celentano (UC Berkeley)
9:55 am–10:20 am		Non-Gaussian Component Analysis: Statistical Query Hardness and its Applications Ilias Diakonikolas (University of Wisconsin-Madison)
10:20 am–10:45 am		SQ Lower Bounds for Learning Halfspaces with Massart Noise Daniel Kane (UC San Diego)
10:45 am–11:10 am		Break
11:10 am–11:35 am		Towards Lower Bounds for Efficient Robust Estimation From Worst Case Assumptions Jerry Li (Microsoft Research)
11:35 am–12:00 pm		Computational Barriers For Learning Some Generalized Linear Models Surbhi Goel (Microsoft Research NY)
12:00 pm–2:00 pm		Lunch
2:00 pm–4:30 pm		Group Hike with Michael Celentano