In fall 2024 a small army of curious undergraduates gathered at ETH Zurich, not to memorize a standard set of theorems but to wrestle with a different beast: average‑case complexity in statistical inference. The notes from that experiment read like a field diary. They describe a teaching format that looks more like a research lab than a traditional classroom, where students split a big project into pieces, master their slice, and then reassemble to prove the whole result. It was not just pedagogy; it was an experiment in how knowledge actually travels inside a university when the subject matter itself is a moving target—the kind of topic where data are noisy, questions are open, and the line between math and algorithm is blurred.
Those notes, authored by Anastasia Kireeva and Afonso S Bandeira, give a blow‑by‑blow of a jigsaw learning technique applied to the frontier topic of average‑case complexity in statistical inference. The idea is deceptively simple: each student becomes an expert on a small piece of a larger proof, and then the class comes back together to combine those pieces into a complete argument. The result is not just a classroom trick; the format mirrors how actual research gets done. Knowledge is dispersed, colleagues teach each other in parallel, and the ultimate test is the group’s ability to assemble a credible, rigorous whole.
Beyond the vibes of a clever classroom hack, the notes illuminate a broader scientific conversation: how we understand what problems are solvable in practice, not just in principle. The field of average‑case complexity asks the blunt question: even when data carry enough information to solve a task, can we do so efficiently on real, noisy instances? It’s a kind of map of terrain that marks both the information threshold and the computational threshold—the moment where a task becomes theoretically possible, yet practically out of reach for quick, scalable algorithms. The ETH notes don’t just catalog ideas; they frame a narrative about the limits of computation in the wild world of statistics, where randomness and high dimensionality are the rules, not the exceptions. The lead researchers, Anastasia Kireeva and Afonso S Bandeira, invite educators and researchers to borrow their format as a way to illuminate these hard questions while training the next generation of thinkers to talk, think, and reason in public about tough topics.
What follows is a guided tour through the core ideas the notes foreground, why they matter, and what the jigsaw experiment teaches about both learning and the kind of scientific stubbornness that makes certain data problems feel almost paradoxical: solvable in theory, stubborn in practice.
ETH Zurich and its Department of Mathematics become the stage on which this experiment plays out. The notes also identify the people who shaped it: lead author Anastasia Kireeva and collaborator Afonso S Bandeira contribute a blend of pedagogy and research framing that makes the piece more than a report on a teaching method. The project is as much about how to teach hard ideas as it is about what those ideas imply for how we understand computation in statistics. The result is a narrative that feels both human and deeply technical, a reminder that the best learning formats can themselves illuminate the hardest questions in the field.
What average‑case complexity really is and why it matters
Traditional computer science often leans on worst‑case guarantees. If you can solve the hardest imaginable input, you can solve almost anything. But the world of real data rarely behaves like the worst case. In statistics and data science, the data we actually see are typically noisy, high‑dimensional, and generated by random processes. That’s where average‑case thinking becomes crucial: it asks not just whether an algorithm can solve a problem in principle, but whether it can do so efficiently on the kinds of instances we’re likely to encounter in practice.
A canonical example that appears in the notes is the planted clique problem on random graphs. You can imagine a graph that has a hidden, unusually large clique inserted into a random background. Information theory might tell you that, in principle, there is enough signal to locate that clique, but the computational reality is harsher: below a certain size, no efficient algorithm reliably finds it. This is the classic statistical‑to‑computational gap—a regime where the information is there, but clever, scalable algorithms fail to exploit it quickly enough. The notes use the planted clique as a schematic to illustrate a broader phenomenon: many problems in high‑dimensional statistics sit in a gray zone where statistical possibility and computational feasibility disagree, sometimes dramatically.
The broader family of problems spans imaging, recommendation systems, and biology. The notes point to real world touchpoints—from cryo‑electron microscopy to modern recommendation engines—where the same tension shows up. If you can tell there’s a signal buried in noise, can you extract it fast enough to be useful? The answer, the notes argue, often depends on the particular structure of the data and the algorithm you’re willing to run. This framing has practical consequences: it nudges researchers to look for exact thresholds, to reason about what counts as “hard” in a noisy world, and to design algorithms that perform as well as theory predicts on typical instances rather than on pathological worst cases.
In short, average‑case complexity reframes how we think about solvability. It shifts the focus from an abstract notion of worst input to a probabilistic landscape of real data. The jigsaw notes anchor this shift to a tangible, human process—the seminar itself—showing that when learning mirrors research, students begin to see the contours of this landscape clearly, often earlier than they would in a conventional course.
The jigsaw seminar as a living lab for hard ideas
The core innovation in the notes is the jigsaw learning format, a cooperative strategy that splits a topic into interlocking parts. In each session, a student presents a background overview, then the class divides into small groups to attack a specific piece of a larger theorem or proof. After a set period, the groups reconvene so that each new team contains a representative of a different part. The groups must then synthesize their partial results into a complete argument. The exercise is not a mere exercise in patience; it creates a built‑in social machine for collaborative reasoning, accountability, and cross‑pollination of ideas.
What makes this particularly effective in a seminar about average‑case complexity is exactly this interdependence. No single student owns the entire, sprawling argument; instead, expertise is distributed, and the final proof only emerges when the pieces fit together. The organizers also included a ritual in which one student acts as the expert of the week, delivering the background and outlining the main questions. The rest of the class then digs into the technical details in the first phase of group work, using the expert as a source of guidance. In the second phase, students reunite by color to share what they learned and push toward finishing the proof together. A simple icebreaker, built on a stochastic block model game, helps students practice local algorithms and the flavor of the problems they will confront in their own proofs.
In practice, the format yielded tangible benefits. The presentations by the expert of the week tended to be more accessible and high level than in traditional seminars, a surprising and welcome outcome. The authors note that this shift likely happens because students in the audience know that the technical heavy lifting will occur in the group work, not in the initial talk. The expert, therefore, can emphasize the big ideas and the intuitive arc of the argument, trusting peers to fill in the fine details later. The result is not merely clearer talks; it is a cultivation of a culture where questions are encouraged and where peer discussion drives deeper understanding.
There is also a clear empirical pay-off: attendees became more engaged, asked more questions, and assumed responsibility for the coherence of the whole argument. Yet the format comes with a price tag in time and planning. The authors report that preparing such sessions required more effort than standard seminars. Still, the payoff—better comprehension, greater participation, and a vivid sense of collective progress—suggests a pedagogical win that could be valuable beyond the specific topic of average‑case complexity.
The icebreaker SBM game, a playful simulation of how communities reveal structure in graphs, embodies the spirit of the approach: local information and collaborative computation can unlock surprising insights. As students negotiate the challenge of recombining their partial results, they get a visceral sense of algorithmic thinking as something that happens through teamwork as much as through individual cleverness. The jigsaw format thus functions as both a teaching tool and a microcosm of how modern statistical inference often unfolds in practice.
The core ideas underneath the surface: a map of the paper’s landscape
The notes sketch a broad map of average‑case complexity that unfolds across 16 well‑defined topics. Rather than presenting a single theorem, they walk through a family of ideas that researchers use to reason about when inference tasks are computationally hard. Some of the central landmarks are as follows, described in approachable terms rather than formal proofs.
First, contiguity and distinguishability. This line of inquiry asks: when are two probabilistic models so similar that no test can reliably tell them apart? The questions hinge on the strength of the signal relative to the noise and on how much of the information in the data is accessible through local tests. The takeaway is not a single threshold but a set of relationships that connect information theory, probability, and computation. In other words, there are regimes where detection is statistically possible but computationally hard, and others where both are easy or both are hard depending on the exact parameters of the problem.
Second, the low‑degree hardness framework. This is a technical lens that tries to predict computational hardness by looking at low‑degree polynomial estimators. If even the best degree D polynomials do not outperform random guessing by a significant margin, then the problem is conjectured to be hard for a wide class of efficient algorithms. This approach connects to ideas from sum‑of‑squares hierarchies and statistical physics, where the geometry of the problem encodes whether easy algorithms can exist or not. It is a striking example of how physics‑style thinking about energy landscapes and fluctuations informs questions about what we can compute efficiently in high dimensions.
Third, the stochastic block model and community detection. The notes narrate how researchers study when we can reliably detect communities in networks and how this changes as we tweak the number of communities, the average degree, and the strength of the signal linking communities. The picture is not that of a single threshold but a phase diagram in which different regions correspond to distinct computational regimes. The message is both practical and theoretical: communities are a natural testbed for ideas about where computation becomes hard, especially when the data is sparse and noisy.
Fourth, the bridge to statistical physics through free energy and MCMC. The free energy, a central object in statistical mechanics, helps connect the dots between information content and the difficulty of finding good estimators. The notes describe how free energy wells can create bottlenecks for Markov chain Monte Carlo, slowing down or even stalling sampling in high‑dimensional inference problems. This is not just a theoretical curiosity; it points to real bottlenecks in practical algorithms, where the landscape of possible solutions can trap naive search strategies and hinder convergence to the true signal.
Fifth, the overlap gap property and ensemble versions. The overlapped geometry of near‑optimal solutions can create a barrier to local search methods. The ensemble overlap gap property, a refined version of the idea, shows up in more complex models like p‑spin glasses and certain planted structures. The upshot is a consistent theme: the geometry of the solution landscape matters as much as the data itself, and when the landscape fragments into disconnected regions, simple heuristics can fail spectacularly even when there is a clear, information‑bearing signal nearby.
Finally, the thread that ties it together is a pragmatic optimism: by systematizing how these ideas are taught and studied, researchers build a shared language for discussing why some problems remain stubbornly hard and how researchers might push the boundaries through creative formats, new theories, or novel algorithms. The notes invite readers to see a line of inquiry that is as much about the shape of the mathematical argument as it is about the actual conclusions, a reminder that science thrives when structure, storytelling, and method align.
All these threads are not isolated curiosities. They sit inside a coherent program that the notes sketch through S1 to S16, a grid of topics that includes contiguity theory, low‑degree hardness for fixed‑rank spikes, the Franz Parisi criterion, MCMC and free energy wells, and the deep geometry of optimization landscapes. The jigsaw structure allows students to navigate these ideas piece by piece, while the reassembly phase reinforces the overarching narrative: to understand what makes statistical inference easy or hard, you must read the data from multiple angles, assemble partial proofs, and test the coherence of the entire argument in a collaborative setting.
The practical takeaway is twofold. For researchers, the framework provides mental models for predicting where algorithms will or will not succeed and for thinking about thresholds not as single numbers but as phases with distinct computational characteristics. For educators, the jigsaw approach demonstrates a powerful way to teach frontiers of mathematics and computer science: when students are asked to teach, to build, and to defend a composite argument, they not only learn the material more deeply but also contribute to a culture of collective problem solving that mirrors real research life.
Why this matters beyond the seminar room
The lessons stretch beyond the specifics of average‑case complexity. They illuminate a broader pattern in modern research: many hard problems sit at the intersection of theory and practice, where randomness and high dimensionality refuse to yield to brute force. Understanding the computational barriers to inference helps researchers set honest expectations about what is doable with current technology and what might require fundamentally new ideas. It also signals to data scientists why certain problems resist scalable solutions even when the data seem to contain enough information to solve them in principle.
In practical terms, the insights feed into how we design algorithms, how we evaluate their performance, and how we communicate limits to non‑experts. They also underscore the value of innovative pedagogy. The students who learned via the jigsaw method not only absorbed deep theoretical material; they practiced asking questions in public, explaining ideas clearly, and rising to the challenge of proving results in a collaborative setting. These are the habits that future researchers will need as data grows more complex and the problems we care about become even more nuanced.
The ETH Zurich notes are also a reminder that some questions are inherently collaborative. The arena of average‑case complexity is not a solitary proving ground but a shared landscape where models, proofs, simulations, and experimental results must fit together. The jigsaw approach helps students experience that reality firsthand, turning abstract puzzles into a tangible, social act of scientific progress. If the method proves scalable to other topics, it could become a standard tool for teaching advanced mathematics and computer science in ways that prepare students to join the chorus of researchers who push the boundaries of what we can know, and what we can do, with data.
