an unknown sparse signal (a vector of length n) from a small number m of linear measurements of it. Equivalently, given an m x n measurement matrix A with m << n and the measurement results b = Az, the problem is to figure out the signal z. This problem has several important applications, for example in medical imaging. If z can be arbitrary, then the problem is hopeless: since m < n, the linear system Ax = b is underde-termined and has an infinite number of solutions (of which z is only one). But many real-world signals are ( approximately) k-sparse in a suitable basis for small k, meaning that ( almost) all of the mass is concentrated on k coordinates.l The main results in compressive sensing show that, under appropriate assumptions on A, the problem can be solved efficiently even when m is only modestly bigger than k (and much smaller than n). 15, 20 One way to prove these results is to formulate a linear programming relaxation of the (NP-hard) problem of computing the sparsest solution to Ax = b, and then show this relaxation is exact.

Planted and Semi-Random Models

Our next genre of models is also inspired by the idea that interesting instances of a problem should have “clearly optimal” solutions, but differs from the stability conditions in assuming a generative model—a specific distribution over inputs. The goal is to design an algorithm that, with high probability over the assumed input distribution, computes an optimal solution in polynomial time.

The planted clique problem. In the maximum clique problem, the input is an undirected graph G = (V, E), and the goal is to identify the largest subset of vertices that are mutually adjacent. This problem is NP-hard, even to approximate by any reasonable factor. Is it easy when there is a particularly prominent clique to be found?

Jerrum27 suggested the following generative model: There is a fixed set V of n vertices. First, each possible edge (u, v) is included independently with l For example, audio signals are typically approximately sparse in the Fourier basis, images in the wavelet basis.

50% probability. This is also known as an Erdös-Renyi random graph with edge density ½. Second, for a parameterk ∈ { 1, 2, . . . , n}, a subset Q ⊆ V of k vertices is chosen uniformly at random, and all remaining edges with both endpoints in Q are added to the graph (thus making Q a k-clique).

How big does k need to be before Q becomes visible to a polynomial-time algorithm? The state of the art is a spectral algorithm of Alon et al., 3 which recovers the planted clique Q with high probability provided k is at least a constant times √n. Recent work suggests that efficient algorithms cannot recover Q for significantly smaller values of k. 11

An unsatisfying algorithm. The algorithm of Alon et al. 3 is theoretically interesting and plausibly useful. But if we take k to be just a bit bigger, at least a constant times √n log n , then there is an uninteresting and useless algorithm that recovers the planted clique with high probability: return the k vertices with the largest degrees. To see why this algorithm works, think first about the sampled Erdös-Renyi random graph, before the clique Q is planted. The expected degree of each vertex is ≈ n/2, with standard deviation ≈√n/2. Textbook large deviation in-equalities show that, with high probability, the degree of every vertex is within ≈√lnn standard deviations of its expectation (Figure 4). Planting a clique Q of size a√n log n, for a sufficiently large constant a, then boosts the degrees of all of the clique vertices enough that they catapult past the degrees of all of the non-clique vertices.

What went wrong? The same thing
that often goes wrong with pure av-
erage-case analysis—the solution is
brittle and overly tailored to a specific
distributional assumption. How can
we change the input model to encour-
age the design of algorithms with more
robust guarantees? Can we find a sweet
spot between average-case and worst-
case analysis?

Semi-random models. Blum and Spencer13 proposed studying semi-random models, where nature and an adversary collaborate to produce an input. In many such models, nature first samples an input from a specific distribution (like the probabilistic planted clique model noted here), which is then modified by the adversary before being presented as an input to an algorithm. It is important to restrict the adversary’s power, so that it cannot simply throw out nature’s starting point and replace it with a worst-case instance. Feige and Killian24 suggested studying monotone adversaries, which can only modify the input by making the optimal solution “more obviously optimal.” For example, in the semi-random version of the planted clique problem, a monotone adversary is only allowed to remove edges that are not in the planted clique Q—it cannot remove edges from Q or add edges outside Q.

Semi-random models with a monotone adversary may initially seem no harder than the planted models that they generalize. But let’s return to the planted clique model with k = Ω(√n log n ), where the “top-k degrees” algorithm succeeds with high probability when there is no adversary. A monotone adversary can easily foil this algorithm in the semi-random planted clique model, by removing edges between clique

Figure 4. Degree distribution of an Erdo″s–Rényi graph with edge density ½, before planting the k-clique Q. If k = Ω (√   (n lg n ), then the planted clique will consist of the k vertices with the highest degrees.

degrees