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.

New and classical results in computational complexity, including interactive proofs, PCP, derandomization, and quantum computation. Ideal for graduate students.

This volume presents the proceedings of the First Canada-France Conference on Parallel Computing; despite its name, this conference was open to full international contribution and participation, as shown by the list of contributing authors. This volume consists of in total 22 full papers, either invited or accepted and revised after a thorough reviewing process. All together the papers provide a highly competent perspective on research in parallel algorithms and complexity, interconnection networks and distributed computing, algorithms for unstructured problems, and structured communications from the point of view of parallel and distributed computing.

Condensed matter systems where interactions are strong are inherently difficult to analyze theoretically. The situation is particularly interesting in low-dimensional systems, where quantum fluctuations play a crucial role. Here, the development of non-perturbative methods and the study of integrable field theory have facilitated the understanding of the behavior of many quasi one- and two-dimensional strongly correlated systems. In view of the same rapid development that has taken place for both experimental and numerical techniques, as well as the emergence of novel testing-grounds such as cold atoms or graphene, the current understanding of strongly correlated condensed matter systems differs quite considerably from standard textbook presentations. The present volume of lecture notes aims to fill this gap in the literature by providing a collection of authoritative tutorial reviews, covering such topics as quantum phase transitions of antiferromagnets and cuprate-based high-temperature superconductors, electronic liquid crystal phases, graphene physics, dynamical mean field theory applied to strongly correlated systems, transport through quantum dots, quantum information perspectives on many-body physics, frustrated magnetism, statistical mechanics of classical and quantum computational complexity, and integrable methods in statistical field theory. As both graduate-level text and authoritative reference on this topic, this book will benefit newcomers and more experienced researchers in this field alike.

This book contains some invited lectures on subjects as diverse as document preparation systems, fractals, number theory, graph colouring and neural networks.

Computational Complexity of Counting and Sampling provides readers with comprehensive and detailed coverage of the subject of computational complexity. It is primarily geared toward researchers in enumerative combinatorics, discrete mathematics, and theoretical computer science. The book covers the following topics: Counting and sampling problems that are solvable in polynomial running time, including holographic algorithms; #P-complete counting problems; and approximation algorithms for counting and sampling. First, it opens with the basics, such as the theoretical computer science background and dynamic programming algorithms. Later, the book expands its scope to focus on advanced topics, like stochastic approximations of counting discrete mathematical objects and holographic algorithms. After finishing the book, readers will agree that the subject is well covered, as the book starts with the basics and gradually explores the more complex aspects of the topic. Features: Each chapter includes exercises and solutions Ideally written for researchers and scientists Covers all aspects of the topic, beginning with a solid introduction, before shifting to computational complexity’s more advanced features, with a focus on counting and sampling

The ubiquitous nature of mobile and pervasive computing has begun to reshape and complicate our notions of space, time, and identity. In this collection, over thirty internationally recognized contributors reflect on ubiquitous computing’s implications for the ways in which we interact with our environments, experience time, and develop identities individually and socially. Interviews with working media artists lend further perspectives on these cultural transformations. Drawing on cultural theory, new media art studies, human-computer interaction theory, and software studies, this cutting-edge book critically unpacks the complex ubiquity-effects confronting us every day. The companion website can be found here: http://ubiquity.dk

These notes are based on a series of lectures given at the Advanced Research Institute of Discrete Applied Mathematics, Rutgers University.

This book presents articles written by leading experts surveying several major subfields in Condensed Matter Physics and related sciences. The articles are based on invited talks presented at a recent conference honoring Nobel laureate Philip W. Anderson of Princeton University, who coined the phrase "More is different" while formulating his contention that all fields of physics, indeed all of science, involve equally fundamental insights. The articles introduce and survey current research in areas that have been close to Anderson's interests. Together, they illustrate both the deep impact that Anderson has had in this multifaceted field during the past half century and the progress spawned by his insights. The contributors cover numerous topics under the umbrellas of superconductivity, superfluidity, magnetism, electron localization, strongly interacting electronic systems, heavy fermions, and disorder and frustration in glass and spin-glass systems. They also describe interdisciplinary areas such as the science of olfaction and color vision, the screening of macroions in electrolytes, scaling and renormalization in cosmology, forest fires and the spread of measles, and the investigation of "NP-complete" problems in computer science. The articles are authored by Philip W. Anderson, Per Bak and Kan Chen, G. Baskaran, Juan Carlos Campuzano, Paul Chaikin, John Hopfield, Bernhard Keimer, Scott Kirkpatrick and Bart Selman, Gabriel Kotliar, Patrick Lee, Yoshiteru Maeno, Marc Mezard, Douglas Osheroff et al., H. R. Ott, L. Pietronero et al., T. V. Ramakrishnan, A. Ramirez, Myriam Sarachik, T. Senthil and Matthew P. A. Fisher, B. I. Shklovskii et al., and F. Steglich et al.

LNCS volumes 2073 and 2074 contain the proceedings of the International Conference on Computational Science, ICCS 2001, held in San Francisco, California, May 27 -31, 2001. The two volumes consist of more than 230 contributed and invited papers that reflect the aims of the conference to bring together researchers and scientists from mathematics and computer science as basic computing disciplines, researchers from various application areas who are pioneering advanced application of computational methods to sciences such as physics, chemistry, life sciences, and engineering, arts and humanitarian fields, along with software developers and vendors, to discuss problems and solutions in the area, to identify new issues, and to shape future directions for research, as well as to help industrial users apply various advanced computational techniques.