Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

For many Constraint Satisfaction Problems by now we have a good understanding of the largest constraint density for which solutions exist. At the same time, though, all known polynomial-time algorithms for these problems stop finding solutions at much smaller densities. We study this phenomenon by examining how the different sets of solutions evolve as constraints are added. We prove in a precise mathematical sense that, for each problem studied, the barrier faced by algorithms corresponds to a phase transition in that problem's solution-space geometry. Roughly speaking, at some problem-specific critical density, the set of solutions shatters and goes from being a single giant ball to exponentially many, well-separated, tiny pieces. All known polynomial-time algorithms work in the ball regime, but stop as soon as the shattering occurs. Besides giving a geometric view of the solution space of random CSPs our results provide novel constructions of one-way functions.