OUP: UK General Catalogue

NEVER MISS AN OXFORD SALE (SIGN UP HERE) |

VIEW BASKET

UK and Europe

Book Catalogue

	Help with online ordering
	How to order
	Postage
	Returns policy
	Search the catalogue
	VAT rates

	Authors
	Description
	Table of Contents

Computational Complexity and Statistical Physics

Edited by Allon Percus, Gabriel Istrate, and Cristopher Moore

Price: £38.00 (paper)
ISBN-13: 978-0-19-517738-1
Publication date: 9 March 2006
384 pages, 84 halftones & line illus., 6-1/8 x 9-1/4 mm
Series: Santa Fe Institute Studies on the Sciences of Complexity
Search for titles in the same series

Ordering

Individual customers may:
order by phone, post, or fax.
Manufactured on Demand - stock will be supplied on a firm sale basis within 28 days

Teachers in UK and European schools (and FE colleges in the UK):

order by phone, post, or fax

Description

Computer science and physics have been closely linked since the birth of modern computing. In recent years, an interdisciplinary area has blossomed at the junction of these fields, connecting insights from statistical physics with basic computational challenges. Researchers have successfully applied techniques from the study of phase transitions to analyze NP-complete problems such as satisfiability and graph coloring. This is leading to a new understanding of the structure of these problems, and of how algorithms perform on them. Computational Complexity and Statistical Physics will serve as a standard reference and pedagogical aid to statistical physics methods in computer science, with a particular focus on phase transitions in combinatorial problems. Addressed to a broad range of readers, the book includes substantial background material along with current research by leading computer scientists, mathematicians, and physicists. It will prepare students and researchers from all of these fields to contribute to this exciting area.

Contents

Preface , Allon G. Percus, Gabriel Istrate, and Cristopher Moore

Part 1: Fundamentals

1. Introduction: Where Statistical Physics Meets Computation , Allon G. Percus, Gabriel Istrate, and

Cristopher Moore

2. Threshold Phenomena and Influence: Perspectives from Mathematics, Computer Science, and Economics , Gil Kalai and Shmuel Safra

Part 2: Statistical Physics and Algorithms

3. Analyzing Search Algorithms with Physical Methods , Simona Cocco, Remi Monasson, Andrea Montanari, and Guilhem Semerjian

4. Constraint Satisfaction by Survey Propagation , Alfredo Braunstein, Marc Mezard, Martin Weigt, and Riccardo Zecchina

5. The Easiest Hard Problem: Number Partitioning , Stephan Mertens

6. Ground States, Energy Landscape and Low-Temperature Dynamics of plus/minus Spin Glasses , Sigismund Kobe and Jarek Krawczyk

Part 3: Identifying the Threshold

7. The Satisfiability Threshold Conjecture: Techniques Behind Upper Bound Improvements , Lefteris M. Kirousis, Yannis C. Stamatiou, and Michele Zito

8. Proving Conditional Randomness Using the Principle of Deferred Decisions , Alexis C. Kaporis, Lefteris M. Kirousis, and Yannis C. Stamatiou

9. The Phase Transition in the Random HornSAT Problem , Demetrios D. Demopoulos, and Moshe Y. Vardi

Part 4: Extensions and Applications

10. Phase Transitions for Quantum Search Algorithms , Tad Hogg

11. Scalability, Random Surfaces and Synchronized Computing Networks , Zoltan Toroczkai, Gyorgy Korniss, Mark A. Novotny, and Hasan Guclu

12. Combinatorics of Genotype-Phenotype Maps: An RNA Case Study , Christian M. Reidys

13. Towards a Predictive Computational Complexity Theory for Periodically Specified Problems: A Survey , Harry B. Hunt, III, Madhav V. Marathe, Daniel J. Rosenkrantz, and Richard E. Stearns

Bibliography

Index

Authors, editors, and contributors

Edited by Allon Percus, Institute for Pure & Applied Mathematics, UCLA, and Los Alamos National Laboratory,
Gabriel Istrate, Los Alamos National Laboratory, and
Cristopher Moore, University of New Mexico and Santa Fe Institute

Links to web resources and related information

More in the same subject area:
Applied mathematics
Theoretical methods
Statistical physics

The specification in this catalogue, including without limitation price, format, extent, number of illustrations, and month of publication, was as accurate as possible at the time the catalogue was compiled. Occasionally, due to the nature of some contractual restrictions, we are unable to ship a specific product to a particular territory. Jacket images are provisional and liable to change before publication.