Average-Case Complexity: From Cryptography to Statistical Learning

Nov 8, 2021 to Nov 10, 2021

Monday, November 8th, 2021
9:45 am–10:00 am		Welcome and Introduction
10:00 am–10:45 am		On Breaking Encryption With A Statistical Zero-Knowledge Oracle Andrej Bogdanov (The Chinese University of Hong Kong)
10:45 am–11:15 am		Break
11:15 am–12:15 pm		Average-Case Hardness Of CSPs Benny Applebaum (Tel-Aviv University)
12:15 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Indistinguishability Obfuscation and Learning Problems Aayush Jain (NTT Research)
3:00 pm–3:30 pm		Break
3:30 pm–4:15 pm		Low-Complexity Cryptography and Simple Hard-to-Learn Functions Yuval Ishai (Technion - Israel Institute of Technology)
4:15 pm–5:15 pm		Reception

Tuesday, November 9th, 2021
10:00 am–10:30 am		On The Hardness Of Average-Case k-SUM Noah Stephens-Davidowitz (Cornell University)
10:30 am–11:00 am		Break
11:00 am–12:00 pm		A Few Simple Average-Case Reduction Techniques And Their Surprising Effectiveness Guy Bresler (MIT)
12:00 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Open Problems Session
3:00 pm–3:30 pm		Break
3:30 pm–4:30 pm		Analyzing Average-Case Complexity by Meta-Complexity Shuichi Hirahara (National Institute of Informatics, Tokyo)

Wednesday, November 10th, 2021
10:00 am–11:00 am		Sum-Of-Squares Lower Bound for Statistical Problems Samuel Hopkins (UC Berkeley)
11:00 am–11:30 am		Break
11:30 am–12:30 pm		Computational trade-offs in graph models Quentin Berthet (University of Cambridge)
12:30 pm–2:00 pm		Lunch
2:00 pm–3:00 pm		Worst-Case Robustness in Machine Learning Aditi Raghunathan (Stanford)
3:00 pm–3:30 pm		Break
3:30 pm–4:30 pm		On the Cryptographic Hardness of Learning Single Periodic Neurons Ilias Zadik (Massachusetts Institute of Technology)