A space-time approach to computational hardness - on the overlap gap property

#writing #math

Survey on the overlap gap property. A really neat way to rule out classes of problems for certain constraint satisfaction problems.
The way I like to think about the general technique is that it proceeds in two steps:

1. Consider the "space-time" of a particular problem. That is, the subset of $2^{\Phi \times X}$ that contains the (problem instance, configuration) pairs such that the configuration satisfies the problem instance.
   Show some properties of the geometry/topology of this set (for instance, that "nearby instances" must have similar solution sets, or that random instances which agree on the first $1-\delta$ fraction of the input might nevertheless have (almost surely) no shared solutions)
2. Show for a certain class of algorithms (e.g. stable algorithm or online-algorithms), that the solution spaces induced by these algorithms must violate the geometry of space time that was shown in part 1.