The adversary who hides the edge

The floors field has had exactly one technique in it. Count the possible answers, observe that each comparison distinguishes at most two cases, conclude that no algorithm can finish in fewer than $\log_2(\text{answers})$ comparisons. For sorting there are $n!$ answers and the bound is $\log_2(n!)$, and merge sort comes within a couple of percent of it.

Ask whether a graph is connected. There are two possible answers.

$\log_2 2 = 1$. The counting argument says: at least one comparison. It is a correct bound and it is worthless, and the reason it is worthless is instructive — the argument’s power comes entirely from the output space being large, and here the output space is a single bit.

So either connectivity is genuinely easy, or a different kind of argument is needed. It is the second, and the argument is one of the most elegant things in the subject.

The argument #

Suppose an algorithm claims to decide connectivity while examining fewer than all $E$ possible edges. Play against it.

The algorithm asks: “is there an edge between $u$ and $v$?” The adversary answers, but the adversary is not holding a graph — it is holding a set of graphs consistent with everything it has said so far, and it answers whichever way keeps that set large and, critically, keeps it containing both a connected graph and a disconnected one.

The algorithm eventually stops and announces an answer. It has not examined some pair $(x, y)$. The adversary now produces two graphs: one that agrees with every answer given and has the edge $xy$, and one that agrees with every answer given and does not. The algorithm behaved identically on both, because it never asked about the only place they differ. Its answer is wrong on one of them.

Therefore no correct algorithm can stop early: every correct connectivity algorithm examines every edge slot. The bound is $\Omega(E)$, and for the dense case, where the algorithm is asking about pairs of vertices rather than reading a list, it is $\Omega(V^2)$ — the property is evasive, meaning every single pair must be probed in the worst case.

Nothing in that argument counts anything. There is no logarithm, no entropy, no decision tree. The bound comes from what the algorithm has not seen.

Why the two techniques are so different #

Set them side by side, because having only one on the site made lower bounds look like a single trick.

Decision tree. A bound on information. Each step of the algorithm yields at most one bit; the answer requires $\log_2 N$ bits; therefore $\log_2 N$ steps. It is a bound on how fast an algorithm can narrow down, and it is strong exactly when the answer space is large.

Adversary. A bound on coverage. The adversary keeps the answer undetermined for as long as the algorithm leaves any input unexamined; therefore the algorithm must examine everything. It is a bound on how much an algorithm can skip, and it is strong exactly when a single unexamined input can flip the answer.

The two are close to opposites in the situations they suit. Sorting has an enormous answer space and no single comparison can flip the whole answer, so counting works and an adversary gains nothing. Connectivity has a two-element answer space and one edge can flip it, so the adversary works and counting gains nothing.

Most interesting problems have neither property cleanly, which is why lower bounds are rare. For a great many, the best known bound is still the trivial “the input has to be read”.

What the algorithms actually spend #

The floor says $E$ edge examinations. Breadth-first search on a connected graph of 2,048 vertices and 6,144 edges examines 12,288.

That is exactly $2E$, and the factor of two is not slack in the algorithm. An undirected edge appears in two adjacency lists, and a traversal that walks every list walks each edge from both ends. Any implementation holding an undirected graph as adjacency lists pays this; the alternative is a representation that stores each edge once and cannot be scanned per-vertex, which nobody wants.

So the honest statement of the distance to the floor is: breadth-first search is at exactly twice the floor, and the factor of two is a property of the representation rather than of the algorithm. That is a much tighter relationship than the sorting field manages for anything except merge sort, and it is tight for a different reason: sorting’s algorithms approach their floor by being clever, and traversal reaches within a factor of two of its floor by having almost nothing to do.

It also means there is no research programme here. In sorting, merge sort at 1.02 says where not to look and the remaining 2% is provably unavailable. In connectivity, the remaining factor of two is available in principle — a CSR structure could scan each edge once given a direction convention — and it is not worth having, because the constant is two and the code becomes wrong for every algorithm that needs both directions.

Where the bound stops applying, which is the interesting part #

An $\Omega(E)$ bound on connectivity sounds final. Three quite ordinary situations get under it, and each gets under it by changing the question rather than by being clever — which is the pattern the floors field keeps finding.

If the graph is already in memory in a structure that answers the question. Maintain a union–find alongside the edge insertions, and connectivity is one comparison of two roots. The $\Omega(E)$ has not been beaten; it has been paid in advance, one edge at a time, during construction. This is the same move as pre-sorting to make search logarithmic: the floor is on the total, and moving work earlier changes when it is spent rather than whether.

If a wrong answer is sometimes acceptable. An algorithm that samples $k$ edges and says “probably connected” is fast and is not solving the problem the bound is about. The adversary argument requires the algorithm to be correct on every input; a randomised algorithm allowed to err with small probability is playing a different game, and for several graph properties the randomised bound is genuinely lower than the deterministic one.

If the question is about a promise. “Decide whether this graph is connected, given that it is either connected or has at least $\epsilon V^2$ edges missing” is a property-testing question, and it can be answered by looking at a constant number of vertices — independent of $V$ entirely. The adversary cannot construct its two graphs, because one of them would violate the promise.

All three are the same manoeuvre in different clothes: the bound is over a set of inputs and a standard of correctness, and shrinking either lowers the floor. A floor is a property of the question, and these are three different questions.

Two more sizes, and the point of drawing them is that nothing in the argument reads the size. The construction is a recipe, and the recipe produces a witness at every $V$.

Evasiveness, and what is still open #

The connectivity bound above is stated for adjacency lists, where the algorithm reads $E$ edge records. There is a sharper version for the adjacency-matrix model, where the algorithm probes pairs and there are $\binom{V}{2}$ of them.

Connectivity in that model is evasive: every one of the $\binom{V}{2}$ pairs must be probed in the worst case, not merely a constant fraction of them. The adversary strategy that proves it is more involved than the one above but the shape is identical.

Evasiveness is not a curiosity. The Aanderaa–Karp–Rosenberg conjecture says that every non-trivial monotone graph property is evasive — every property that cannot be destroyed by adding edges, and that is not constant, requires all $\binom{V}{2}$ probes. It is known for prime $V$ by a topological argument of Kahn, Saks and Sturtevant, and it is open in general. That is worth stating in a field about floors, because it is a place where the floor is conjectured rather than known, and the site’s other floor is a two-line theorem from 1950s information theory.

The contrast is the useful part. Sorting’s floor is exact, provable in a paragraph, and matched to within 2%. Connectivity’s floor is provable in a paragraph in one model, matched to within a factor of two, and its sharpest form is a fifty-year-old open problem. Neither is typical, and having both stops the field from suggesting that lower bounds come in one flavour.

The sorting bound, recast #

The two techniques look like different subjects, and they are not: the sorting bound can be proved by an adversary too, and seeing it done makes the relationship between them clear.

The adversary holds a set of permutations consistent with every answer it has given so far. It starts with all $n!$ of them. When the algorithm asks whether $a_i < a_j$, the adversary answers in whichever direction leaves more permutations alive — and since every permutation is in one camp or the other, one of the two directions leaves at least half.

So after $k$ comparisons at least $n!/2^k$ permutations remain consistent. The algorithm cannot stop while two remain, because two consistent permutations mean two different correct outputs and it must produce one of them. Therefore $n!/2^k < 2$, giving $k > \log_2(n!) - 1$.

That is the same bound, from the same starting point, argued the other way round. The decision-tree version counts leaves and bounds the depth; the adversary version keeps the candidate set large and bounds the number of halvings. They are dual statements about one quantity.

What the recasting shows is where the two techniques actually differ, and it is not the mathematics. It is what the adversary is allowed to withhold.

In sorting, the adversary withholds the ordering and the algorithm’s questions each remove at most half the possibilities. The set shrinks geometrically, so a logarithmic number of questions suffices and the bound is logarithmic.

In connectivity, the adversary withholds one edge and the algorithm’s questions remove nothing until it asks about that specific edge. The set does not shrink geometrically; it stays ambiguous until the last unexamined input is examined, and the bound is linear in the number of inputs.

Geometric shrinkage gives a logarithm; no shrinkage at all gives coverage. Every lower bound of either kind is somewhere between those two, and knowing which end a problem is near is the first thing to establish about it.

What the adversary cannot do #

An adversary argument bounds deterministic algorithms, and stating why is worth a section because the gap is where a great deal of modern algorithm design lives.

The argument’s move is: the algorithm’s next question is determined by the answers so far, so the adversary knows it in advance and can prepare. Against a randomised algorithm that step fails. The adversary does not know which question is coming, so it cannot arrange for the undetermined input to be the one that is skipped — it can only make that likely, and “likely” is not what a correctness proof needs.

The consequence is not that randomisation beats every lower bound. For connectivity it does not: reading every edge is still required, because a randomised algorithm that skips edges gets the answer wrong with positive probability on some input, and an algorithm allowed to be wrong is solving a different problem. What changes is that the technique stops applying, and a separate argument is needed.

The standard replacement is Yao’s principle, and its shape is elegant enough to state. To lower-bound a randomised algorithm’s expected cost on the worst input, choose a distribution over inputs and lower-bound the expected cost of the best deterministic algorithm on that distribution. The two are related by a minimax argument, and the second is a question about deterministic algorithms again — which is to say, the technique for bounding randomised algorithms is to find the right distribution and then use the deterministic techniques.

That is worth knowing here because it explains a pattern in this site’s other field. Randomising a pivot defeats an adversary who chooses the input, and it does not lower the expected cost by a single comparison — randomised quicksort’s mean at $n = 512$ is 4,946 against the first-element rule’s 4,935 on random input. Randomisation moved the guarantee from “fast if the data is nice” to “fast unless the coin flips go badly”, and bought nothing in expectation. The adversary framing is exactly what makes that trade legible: what was purchased is immunity to an opponent, not speed.

Two floors that are not adversary arguments #

Worth a short note, because the pattern of “one technique per field” is what this essay is arguing against and two more techniques are close by.

Reduction. Most lower bounds in practice are neither counting nor adversary arguments; they are reductions. Show that solving problem A quickly would solve problem B quickly, and inherit B’s bound. The sorting bound propagates this way to element uniqueness, to convex hull, and to a great deal else, and none of those results is proved directly.

Communication. For a bound on a distributed or streaming computation, the argument is usually that some quantity of information must cross a boundary. That is neither a count of outputs nor an adversary withholding an input; it is a count of bits on a wire, and it is the technique behind most streaming lower bounds.

Neither is measurable at this site’s scale and both belong in a list of what a lower bound can be, because the field’s two examples — one counting, one adversary — do not span the subject and this essay would be misleading if it left the impression that they did.

The certificate is a sixth of the floor #

There is a gap between the bound and the answer that the adversary argument makes vivid and does not name, and it is worth a section because it is where most of algorithm design actually happens.

The bound is on finding the answer. It is not a bound on checking one, and for connectivity the two are wildly apart in both directions.

A spanning tree certifies connectivity. Hand somebody $V-1$ edges and they can verify in $V-1$ steps that these edges join every vertex — no reference to the rest of the graph at all. On the measured graph that is 2,047 edges, against the 12,288 list entries breadth-first search reads to produce it. The certificate is a sixth of what it costs to find.

And a closed set certifies disconnection. Hand somebody a set $S$ of vertices and the claim that no edge leaves it, and they check by reading $S$’s adjacency lists and nothing else — which for a small component is a handful of entries out of six thousand.

So both answers have certificates far below $\Omega(E)$, and the floor is untouched by that, because a certificate has to be found before it can be checked. That is the ordinary state of affairs and it is easy to lose sight of when a bound is quoted as though it were about the problem rather than about the search.

The disconnection certificate has a second consequence the page states for the matrix model and not for lists: the $\Omega(E)$ is worst-case, and the best case is a constant. Breadth-first search from a vertex in a small component reads that component’s lists, finds it reaches fewer than $V$ vertices, and answers — having examined none of the edges among the other two thousand. It is correct, because reaching fewer than every vertex proves disconnection whatever the unread edges say.

So the adversary’s construction is not describing every input; it is describing the hard ones, and the hard ones are the connected graphs and the graphs that are one edge from connected. Every graph comfortably far from the boundary is cheap. That is the same structure as the floor moves when the question does’s argument, arriving inside one question rather than between four: the floor is over a set of inputs, and most members of the set are nowhere near it.

Which puts the factor of two in its place. Breadth-first search is at $2E$ on a connected graph, at the floor’s constant on the worst input, and at essentially nothing on a graph that falls apart early — so twice the floor is the price of the worst case and not the price of a run. How close anything gets to the floor reports sorting’s distance as a single ratio because sorting’s cost barely moves across inputs; connectivity’s ratio needs an input named beside it, and the range is the whole graph.

The adversary as a way of thinking #

The technique generalises past lower bounds, and it is worth naming the generalisation because it is what makes the argument feel like a tool rather than a trick.

An adversary argument is: assume the input is not fixed until it has to be. The opponent is not withholding information out of malice, it is refusing to commit, and it commits at the last possible moment in whichever way hurts most.

That is the same posture behind several things already on this site. Randomising a pivot is a defence against exactly this opponent, and it works by making the algorithm’s choices unavailable to it. The lower bound on comparison sorting can be recast in adversary form — answer each comparison in whichever direction leaves more permutations alive, and the algorithm needs $\log_2(n!)$ questions to get the survivor count down to one — and the recast version is the same theorem with a different proof.

What the adversary framing adds, in every case, is a way to ask what has this algorithm not yet ruled out. That question is answerable when “how many bits has it acquired” is not.