Computational Complexity and Local Algorithms: On the Interplay Between Randomness and Computation

This volume contains a collection of studies in the areas of complexity theory and local algorithms. A common theme in most of the papers is the interplay between randomness and computation. This interplay is pivotal to some parts of complexity theory and is essential for local algorithms.

The works included address a variety of topics in the areas of complexity theory and local algorithms. Within complexity theory the topics include approximation algorithms, counting problems, enumeration ...