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.