Easy, Hard, and Impossible: The Three Phases

The previous lesson set up a single control parameter: how much data you have per unknown. The natural expectation is one threshold, below which recovery fails and above which it works.

The central discovery of this field is that there are often two.

The information-theoretic threshold is where the signal becomes recoverable in principle. Below it the data genuinely does not determine the answer; the posterior spreads over many possibilities and no procedure can distinguish them. Above it the Bayes-optimal estimator succeeds.

The algorithmic threshold is where efficient algorithms start working.

When these coincide, the world behaves as intuition expects. When they separate, a third regime opens between them where the information is present, the answer is uniquely determined, and every known polynomial-time algorithm fails.

That middle band is the hard phase. It is the most interesting object in this subject, and the rest of this lesson is about what lives there.

Naming the regimes precisely is worth doing, because the distinctions are easy to blur.

Impossible. Below the information-theoretic threshold. The observed data is statistically consistent with many different ground truths, so no estimator, given unlimited computation, beats chance. Failure here is a property of the data.

Hard. Between the two thresholds. The information is sufficient: an exhaustive search over all candidates would identify the planted signal. But exhaustive search takes exponential time, and every known efficient algorithm fails. Failure here is a property of computation.

Easy. Above the algorithmic threshold. Efficient algorithms recover the signal, often something as simple as a spectral method.

The practical significance is that these three look identical from the outside. In all three your algorithm returns garbage. Only the theory tells you whether collecting more data is the answer, whether a better algorithm might exist, or whether you should abandon the problem.

One axis, two thresholds, three regimes. The diagnosis you need is which regime you are in, because the correct response differs completely: more data, a better algorithm, or nothing.

The result that opened this field concerns the stochastic block model, and it came from physicists.

Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborova published "Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications" in Physical Review E volume 84, article 066106, in 2011.

Using the cavity method from statistical physics, they obtained an asymptotically exact analysis of the model's phase diagram, describing both the detectability transition and the easy-to-hard transition.

Their conjecture became the organising statement of the area. Detecting clusters in the symmetric block model in polynomial time is possible above the Kesten-Stigum threshold. Below that threshold, detection remains possible information-theoretically, though not necessarily efficiently, when the number of communities is at least four.

Read the last clause carefully, because it is the surprising part. With two or three communities the thresholds coincide and there is no hard phase. At four or more, they separate and a genuine information-computation gap opens.

A problem can therefore be easy or hard depending on a parameter that has nothing to do with how much data you have.

Community detection has a subtle gap. Planted clique has a spectacular one, which is why it became the field's reference problem.

The setup is minimal. Take a random graph on n vertices where each edge is present independently with probability one half. Choose k vertices and add all edges among them, making them a clique. Given the graph, find the planted clique.

The two thresholds are far apart.

The statistical threshold sits at roughly $k = 2\log_2 n$. Above that size the planted clique is larger than any clique that would occur by chance, so it is identifiable: enumerate all subsets of that size, check each, and the planted one stands out. That enumeration is astronomically slow, but it establishes that the information is there.

The computational threshold for the best known polynomial-time algorithms sits at roughly $k \geq \epsilon\sqrt{n}$.

Compare the scales. For n around a million, the statistical threshold is a clique of about 40 vertices, while efficient algorithms need something on the order of a thousand. The hard phase spans that entire range, and decades of effort have not produced an algorithm that enters it.

The physics picture explains the mechanism, and it is genuinely illuminating.

Think of the posterior distribution as a landscape over candidate solutions, where height is how well a candidate explains the data. Algorithms are local: they start somewhere and improve.

In the easy phase, the landscape has a single dominant basin containing the true signal, and its pull extends across the space. Any reasonable local method slides into it.

In the hard phase, the true signal still sits at the global optimum, so the information is present. But the landscape around it is fractured into exponentially many spurious local optima, separated by barriers. A local algorithm starting from a random point falls into one of these and stops. The global optimum exists and is correct, but nothing points toward it from where you are.

The transition between these landscapes is what physicists call a discontinuous phase transition. Zdeborova's work highlights precisely this link: discontinuous transitions are associated with algorithmic hardness and shape the behaviour of gradient-based methods.

The correspondence is now a design principle. Look at the landscape geometry, and you can predict whether local algorithms will work.

A sceptic should ask the obvious question: how do we know the hard phase is not just a gap in our imagination, waiting for someone clever?

Nobody has proven it is not, and that should be stated plainly. But the evidence has accumulated from independent directions that agree.

Physics predictions. The cavity and replica methods predict exact threshold locations, and many have since been confirmed by rigorous proofs.

Sum-of-squares lower bounds. Barak and colleagues (2016) proved a tight computational lower bound for planted clique within the sum-of-squares hierarchy, a powerful and general family of algorithms.

The low-degree polynomial framework. This is the most striking convergence. Many state-of-the-art algorithms, including spectral methods and approximate message passing, can be written as low-degree polynomial functions of the data. Analysing what such polynomials can achieve turns out to reproduce the conjectured computational thresholds across planted clique, sparse PCA, community detection, and tensor PCA.

Average-case reductions. Results such as Brennan and Bresler's work on reductions to sparse PCA connect these problems, so hardness of one implies hardness of others.

Four methodologies with different assumptions, drawing the same boundary.

The framework yields a practical diagnostic, provided you are honest about what transfers.

The last row is the signature worth recognising. Sharp, sudden improvement from a modest increase in data is the fingerprint of a phase transition, and it means the useful lever is data quantity, not model architecture.

Two honest caveats. Your problem is probably not one of the exactly-solved models, so treat this as a lens rather than a calculation. And the thresholds are asymptotic, so at finite size the transition is smoothed and its location shifts.

What the framework changes is the question you ask when things fail: not "what should I try next?" but "which resource am I short of?"