Average-Case Complexity: From Cryptography to Statistical Learning

Program

Computational Complexity of Statistical Inference

Location

Calvin Lab Auditorium

Date

Monday, Nov. 8 – Wednesday, Nov. 10, 2021

Back to calendar

9:45 – 10 a.m.

Welcome and Introduction

10 – 10:45 a.m.

On Breaking Encryption With A Statistical Zero-Knowledge Oracle

Andrej Bogdanov (The Chinese University of Hong Kong)

10:45 – 11:15 a.m.

Break

11:15 a.m. – 12:15 p.m.

Average-Case Hardness Of CSPs

Benny Applebaum (Tel-Aviv University)

12:15 – 2 p.m.

Lunch

2 – 3 p.m.

Indistinguishability Obfuscation and Learning Problems

Aayush Jain (NTT Research)

3 – 3:30 p.m.

Break

3:30 – 4:15 p.m.

Low-Complexity Cryptography and Simple Hard-to-Learn Functions

Yuval Ishai (Technion - Israel Institute of Technology)

4:15 – 5:15 p.m.

Reception

10 – 10:30 a.m.

On The Hardness Of Average-Case k-SUM

Noah Stephens-Davidowitz (Cornell University)

10:30 – 11 a.m.

Break

11 a.m. – 12 p.m.

A Few Simple Average-Case Reduction Techniques And Their Surprising Effectiveness

Guy Bresler (MIT)

12 – 2 p.m.

Lunch

2 – 3 p.m.

Open Problems Session

3 – 3:30 p.m.

Break

3:30 – 4:30 p.m.

Analyzing Average-Case Complexity by Meta-Complexity

Shuichi Hirahara (National Institute of Informatics, Tokyo)

10 – 11 a.m.

Sum-Of-Squares Lower Bound for Statistical Problems

Samuel Hopkins (UC Berkeley)

11 – 11:30 a.m.

Break

11:30 a.m. – 12:30 p.m.

Computational trade-offs in graph models

Quentin Berthet (University of Cambridge)

12:30 – 2 p.m.

Lunch

2 – 3 p.m.

Worst-Case Robustness in Machine Learning

Aditi Raghunathan (Stanford)

3 – 3:30 p.m.

Break

3:30 – 4:30 p.m.

On the Cryptographic Hardness of Learning Single Periodic Neurons

Ilias Zadik (Massachusetts Institute of Technology)