Computational Complexity and Statistical Physics

Allon G. Percus, Gabriel Istrate, and Cristopher Moore: Preface Part 1: Fundamentals 1: Allon G. Percus, Gabriel Istrate, and Cristopher Moore: Introduction: Where Statistical Physics Meets Computation 2: Gil Kalai and Shmuel Safra: Threshold Phenomena and Influence: Perspectives from Mathematics, Computer Science, and Economics Part 2: Statistical Physics and Algorithms 3: Simona Cocco, Remi Monasson, Andrea Montanari, and Guilhem Semerjian: Analyzing Search Algorithms with Physical Methods 4: Alfredo Braunstein, Marc Mezard, Martin Weigt, and Riccardo Zecchina: Constraint Satisfaction by Survey Propagation 5: Stephan Mertens: The Easiest Hard Problem: Number Partitioning 6: Sigismund Kobe and Jarek Krawczyk: Ground States, Energy Landscape and Low-Temperature Dynamics of plus/minus Spin Glasses Part 3: Identifying the Threshold 7: Lefteris M. Kirousis, Yannis C. Stamatiou, and Michele Zito: The Satisfiability Threshold Conjecture: Techniques Behind Upper Bound Improvements 8: Alexis C. Kaporis, Lefteris M. Kirousis, and Yannis C. Stamatiou: Proving Conditional Randomness Using the Principle of Deferred Decisions 9: Demetrios D. Demopoulos, and Moshe Y. Vardi: The Phase Transition in the Random HornSAT Problem Part 4: Extensions and Applications 10: Tad Hogg: Phase Transitions for Quantum Search Algorithms 11: Zoltan Toroczkai, Gyorgy Korniss, Mark A. Novotny, and Hasan Guclu: Scalability, Random Surfaces and Synchronized Computing Networks 12: Christian M. Reidys: Combinatorics of Genotype-Phenotype Maps: An RNA Case Study 13: Harry B. Hunt III, Madhav V. Marathe, Daniel J. Rosenkrantz, and Richard E. Stearns: Towards a Predictive Computational Complexity Theory for Periodically Specified Problems: A Survey Bibliography Index