David Garmanik
Performance of local algorithms in random structures. Power and limitations.
Abstract: We will give an overview of the performance of local
algorithms in solving combinatorial optimization problems in random
settings. For many such problems, the solution space geometry exhibits
a phase transition. Below this transition simple local algorithms are
as effective as any algorithms we can analyze, whereas above the phase
transition, the solution space exhibits a complicated landscape which
creates a provable obstacle for the performance of local
algorithms. It is conjectured that in fact no polynomial time
algorithms exist above the phase transition.