Cristopher Moore

Life and career

Cristopher Moore, born in 1968, is one of the few people in this roster who is genuinely bilingual across physics and computer science — not as a matter of interdisciplinary posturing but because he was formally trained in one and then made a career in the other. He took his undergraduate degree at Northwestern and a PhD in physics from Cornell, working in the orbit of nonlinear dynamics and complex systems. That formation matters enormously for understanding his output. Physicists are taught to look for *order parameters* and *critical points*: to ask, as a control knob is turned, at what value does the qualitative character of the system suddenly change? Computer scientists are taught to ask what is computable and at what cost. Moore's entire research program consists of asking the physicist's question about the computer scientist's objects.

He spent a formative period at the **Santa Fe Institute**, the interdisciplinary research center in New Mexico devoted to complex systems, where he has been a resident professor. He also held a faculty appointment at the University of New Mexico, in both computer science and physics. Santa Fe is an unusual institution — small, permanently temporary, organized around visitors and cross-disciplinary conversation rather than departments — and it suits Moore, whose work consistently sits in the gaps between fields. He has been active in the study of random constraint satisfaction, statistical inference on networks, quantum computation, and, more recently, algorithmic fairness and the use of predictive models in criminal justice.

In 2011 he and Stephan Mertens published *The Nature of Computation* with Oxford University Press. It is a nearly thousand-page textbook that has become something of a cult object: a book on computational complexity written to be *read*, with genuine intellectual generosity toward the reader, covering the standard theory alongside material — random graphs, phase transitions, spin glasses, quantum computing, the physics of message passing — that no other complexity text attempts to integrate. It won the American Publishers' PROSE award and has been widely praised as one of the best-written technical books in the field. For many graduate students it is the place they first encounter the idea that hardness is not uniform across instances but concentrates near a critical point.

Moore is also visible as a public scientist, writing and speaking about algorithmic decision-making, and has been an outspoken participant in debates about risk-assessment tools in the justice system — a topic where his statistical-physics instinct for asking "what does this measurement actually determine?" turns out to be exactly the right one.

Key contributions

**Phase transitions in random satisfiability.** The central object here is random $k$-SAT: generate a Boolean formula by picking $m$ clauses of $k$ literals uniformly at random over $n$ variables, and let $\alpha = m/n$ be the clause density. As $\alpha$ increases, the formula goes from almost surely satisfiable to almost surely unsatisfiable — and the transition is *sharp*, occurring in a vanishing window around a critical $\alpha_c$ as $n \to \infty$. Empirically and theoretically, the instances that are computationally hardest cluster right at that threshold; far below it, solutions are abundant and easy to find, and far above it, unsatisfiability is easy to certify.

Moore's contribution, with a range of collaborators, has been both to prove rigorous bounds on such thresholds and to translate the physicists' non-rigorous but predictive machinery — the replica method, the cavity method, survey propagation — into arguments computer scientists can inspect and, in some cases, verify. The deeper structural picture that emerged is that the solution space itself undergoes transitions before the satisfiability threshold: solutions first form a single connected cluster, then shatter into exponentially many well-separated clusters (the *clustering* or *dynamical* transition), then condense onto a few dominant clusters. Local search algorithms fail once shattering occurs, because the solution space stops being navigable by local moves. This gives a physical explanation of algorithmic hardness that pure worst-case complexity theory cannot provide.

**Detectability thresholds in community detection.** Moore's most influential recent work concerns the stochastic block model — a random graph in which nodes carry hidden group labels and edge probabilities depend on those labels. The question is: given the graph, can you recover the labels? The striking answer, developed by Decelle, Krzakala, Moore, and Zdeborová and then established rigorously in a line of work Moore has helped drive, is that there is a sharp **detectability threshold**. Below a critical signal strength — expressed in terms of the difference between within-group and between-group edge probabilities relative to the average degree — no algorithm, however powerful, can do better than chance at recovering the communities. The information is simply not in the data. Above it, belief propagation succeeds and does so efficiently.

This is a conceptually important result for anyone doing inference on networks, because it changes the character of a negative result. When your community-detection algorithm returns nothing meaningful, the question "is my algorithm too weak, or is there nothing there?" now has a principled answer. Moore's survey "The Computer Science and Physics of Community Detection" is the standard entry point. The same framework has produced *information-computation gaps*: regimes where the signal is statistically detectable in principle but no known polynomial-time algorithm finds it, a phenomenon now recognized across sparse PCA, planted clique, tensor decomposition, and many high-dimensional inference problems.

**Random graphs, quantum computation, and breadth.** Moore has also worked on thresholds in random graph structures more generally, on the computational power of quantum circuit classes, on quantum algorithms for hidden subgroup problems, and on the dynamics of cellular automata and one-dimensional systems. The breadth is genuine rather than shallow; he tends to enter a field, find the phase-transition question inside it, and answer that.

In battle

Moore's computed profile is among the strongest and most balanced on the roster. He carries 102 problems at a mean of **47.8** — the highest of the theorists here — with thirteen dominant problems, nineteen at 70 or above, and only twelve at or below 20. Where Cook and Blum are scalpels, Moore is a broadsword. His top categories are **computability** (72.9 over sixteen problems), **causality** (69.0), **networks** (67.3 over fifteen problems), **high-dim** (48.0), **search** (47.3), and **optimization** (46.0). That networks average is the standout: no other theorist here comes close, and it is a direct consequence of the community-detection and random-graph work.

His two ceiling problems are exactly what you would predict. **P034, "Phase transition at the threshold"** (96) is his home turf in the most literal sense — random $k$-SAT, clause-to-variable ratio, why hardness concentrates at the critical point. **P090, "The communities in the graph"** (96) is the stochastic block model and the detectability threshold, which is his own result. **P189, "Climb out of the local trap"** (90) rewards his understanding of why local search fails — the solution-space shattering picture is precisely an account of when hill-climbing gets stuck and why. **P271, "Robust to failure, fragile to attack"** (90) is percolation and network resilience, a random-graph threshold question in applied dress. **P093, "The random graph's threshold"** (85) is Erdős–Rényi threshold phenomena. He is also strong on **P162, "More time, strictly more power"** (86), **P163, "The fastest-growing function"** (85), and **P164, "Trust without recomputing"** (84), reflecting the fact that *The Nature of Computation* required him to master the whole of classical complexity theory in order to write it.

His weaknesses cluster tightly in classical statistics and applied modeling. **P143, "The coefficient that flips sign"** (10) is his floor — confounding, mediation, and collider bias, the Pearl/Rubin causal-inference machinery, which he has never worked in directly. **P234, "Where did every pixel go?"** (12) is optical flow; **P145, "Just look at the neighbors"** (12) is $k$-nearest-neighbors classification; **P250, "The cluster that iterates"** (13) is $k$-means; **P138, "The trend with a memory"** (13) is time-series with autocorrelation; **P128, "Does the extra parameter earn its keep?"** (14) is model selection via information criteria. His `regression` (11.5), `perception` (13.5), and `nlp` (15.0) averages are the bottom of his card.

Note the interesting tension in his profile: `causality` scores 69.0 as a *category average* while the specific confounding problem scores 10. The high causality average comes from problems where the causal question is really a network or threshold question — where structure and percolation carry the answer — not from problems requiring the do-calculus or potential-outcomes formalism.

The stated battle identity is honest about the real limitation: Moore wins by locating the cliff-edge between easy and hard, and loses inside regimes where physics intuition outruns available proofs. He is the roster's best generalist theory pick and the single best fighter for anything involving randomness on graphs, thresholds, or the boundary between what is statistically possible and computationally achievable.