Heavy-tailed Phenomena in Computation

In recent years, it has become clear that extreme events often occur much more frequently than standard statistical models would predict. Such non-standard distributions have recently been observed in areas as diverse as economics, statistical physics, and geophysics. Computational processes are also characterized by extreme fluctuations. In fact the runtime distributions of computational search methods exhibit intriguing properties, often characterized by very long tails or "heavy tails". I will discuss how one can dramatically boost the performance of computational search procedures for solving real-world problems by exploiting the heavy tailed phenomena. I will also discuss formal models of heavy-tails in combinatorial search and discuss different "statistical regimes of heavy-tailed behavior" in combinatorial domains, providing a general characterization of parameter regions where heavy-tailed behavior is prevalent.