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

CREATORAnastasia Kireeva, Afonso S. Bandeira
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE172 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-22182

Browse the full library · About the Tower of Babel