Average-case complexity in statistical inference: A puzzle-driven research seminar
Anastasia Kireeva, Afonso S. Bandeira · 2025
Read Average-case complexity in statistical inference: A puzzle-driven research seminar by Anastasia Kireeva, Afonso S. Bandeira (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-22182.txt.
Introduction
Anastasia Kireeva and Afonso Bandeira describe running a graduate seminar at ETH Zurich where students learned recent research on the hidden costs of statistical inference. The topic, average-case complexity, asks when problems that are solvable in principle stay hard for typical data. The seminar used the jigsaw method: small groups each mastered one piece of a proof, then regrouped to teach each other.
Sessions opened with a student presentation, then moved to the group work on current research papers. The authors report higher engagement, more approachable talks, and livelier discussion than in a standard lecture format. They include the exercise sheets in an appendix. Other teachers can lift them for courses on statistical-to-computational gaps. The notes are part teaching report, part shared course material.
Catalog record
| CREATOR | Anastasia Kireeva, Afonso S. Bandeira |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 172 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-22182