how lower bounds motivate randomization and approximation
A lower bound can feel like a dead end: someone proves your problem cannot be solved faster than Omega(n log n), or — worse — that it is NP-hard, and it seems the project is over. But a good lower bound is really a map. It tells you exactly which assumption you must give up to make progress, because it always holds only under specific rules. Change the rules thoughtfully and the wall has a door. Lower bounds do not end research; they redirect it.
There are several standard doors, each weakening a different premise of the bound. Change the model: the comparison-sorting Omega(n log n) assumes you only compare keys, so if keys are small integers you switch to counting or radix sort and get O(n) — you escaped by reading values, not just comparing. Accept approximation: many optimization problems are NP-hard to solve exactly, so you ask for a provably near-optimal answer instead, like a 2-approximation for vertex cover that runs in polynomial time. Use randomness: a deterministic worst-case bound may be dodged by an algorithm that flips coins, getting a good EXPECTED running time (randomized quicksort) or a correct answer with high probability (Monte Carlo primality testing). Restrict the inputs: a bound that needs adversarial inputs may not bind on the special cases you actually care about, like nearly-sorted data or planar graphs. Relax the guarantee: settle for the average case, or amortized cost, or streaming with bounded memory.
The honest framing is that each door has a price you must state plainly. Approximation gives up exactness — a 2-approximation can be a factor 2 from optimal in the worst case, not merely 'close'. Randomization trades determinism for probability — randomized quicksort's O(n log n) is only the EXPECTED time; its worst case is still O(n^2), and a Monte Carlo method can be wrong with small probability. Special-case algorithms only help on those special cases. So lower bounds are not defeatist; they are the precise reason these whole subfields — approximation algorithms, randomized algorithms, parameterized and average-case analysis — exist at all. Knowing exactly what is impossible is what tells you which compromise to make.
Sorting 32-bit integers: the Omega(n log n) comparison bound seems to cap you at n log n. But that bound assumes comparisons only. Radix sort reads the keys' digits, sidestepping the model, and sorts in O(n) for fixed-width integers. The lower bound did not block progress — it told you to stop comparing and start reading bits.
A lower bound names the assumption to drop: change model, approximate, randomize, or specialize.
Each escape has a stated price: approximation loses exactness (a 2-approx can really be 2x off), randomization gives only expected time or high-probability correctness, and special-case speedups vanish off their special case. A lower bound redirects effort; it does not grant a free lunch.