View:

- no detail
- some detail
- full detail

## Information, Physics, and Computation

*Marc Mézard and Andrea Montanari*

- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- book

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

This book presents a unified approach to a rich and rapidly evolving research domain at the interface between statistical physics, theoretical computer science/discrete mathematics, and ... More

## INTRODUCTION TO FIXED-PARAMETER ALGORITHMS

*Rolf Niedermeier*

### in Invitation to Fixed-Parameter Algorithms

- Published in print:
- 2006
- Published Online:
- September 2007
- ISBN:
- 9780198566076
- eISBN:
- 9780191713910
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198566076.003.0001
- Subject:
- Mathematics, Combinatorics / Graph Theory / Discrete Mathematics

This chapter discusses three introductory examples for studying exact and fixed-parameter algorithms. It starts with the boolean Satisfiability problem and its numerous parameters, then discusses an ... More

## Satisfiability

*Marc Mézard and Andrea Montanari*

### in Information, Physics, and Computation

- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0010
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

Because of Cook's theorem, satisfiability lies at the heart of computational complexity theory. This chapter presents some selected research directions, focusing on ensembles of random satisfiability ... More

## The 1RSB cavity method

*Marc Mézard and Andrea Montanari*

### in Information, Physics, and Computation

- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0019
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

In graphical models whose factor graph has a locally tree-like structure, belief propagation may fail because variables become correlated at large distances. This phenomenon has been observed in many ... More

## Random K-satisfiability

*Marc Mézard and Andrea Montanari*

### in Information, Physics, and Computation

- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0020
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

This chapter studies an ensemble of random satisfiability problems, ‘random K-satisfiability’ (K-SAT). Applying the 1RSB cavity method, it first derives the phase diagram in the limit of large N, in ... More

## Introduction to combinatorial optimization

*Marc Mézard and Andrea Montanari*

### in Information, Physics, and Computation

- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780198570837
- eISBN:
- 9780191718755
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198570837.003.0003
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

This chapter provides an elementary introduction to some basic concepts in theoretical computer science. It includes basic notions of graph theory and an informal introduction to computational ... More

## Optimization Problems

*Hidetoshi Nishimori*

### in Statistical Physics of Spin Glasses and Information Processing: An Introduction

- Published in print:
- 2001
- Published Online:
- January 2010
- ISBN:
- 9780198509417
- eISBN:
- 9780191709081
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198509417.003.0009
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics ... More

## Computing: The Turing way

*Massimiliano Di Ventra*

### in MemComputing: Fundamentals and Applications

- Published in print:
- 2022
- Published Online:
- March 2022
- ISBN:
- 9780192845320
- eISBN:
- 9780191937521
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780192845320.003.0002
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

This Chapter introduces the Turing paradigm of computation and computational complexity classes. It discusses the algorithmic way combinatorial optimization problems are traditionally solved and ... More

## Application to combinatorial optimization problems

*Massimiliano Di Ventra*

### in MemComputing: Fundamentals and Applications

- Published in print:
- 2022
- Published Online:
- March 2022
- ISBN:
- 9780192845320
- eISBN:
- 9780191937521
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780192845320.003.0009
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

This Chapter discusses a wide variety of combinatorial optimization problems where the numerical solution of the ordinary differential equations of DMMs shows advantages over traditional algorithms.

## Still Life Theory

*Matthew Cook*

### in New Constructions in Cellular Automata

- Published in print:
- 2003
- Published Online:
- November 2020
- ISBN:
- 9780195137170
- eISBN:
- 9780197561652
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/9780195137170.003.0008
- Subject:
- Computer Science, Systems Analysis and Design

In Conway’s Game of Life [2], if one starts with a large array of randomly set cells, then after around twenty thousand generations one will see that all motion has died down, and only stationary ... More

## Opting for the Best

*Douglas W. Portmore*

### in Opting for the Best: Oughts and Options

- Published in print:
- 2019
- Published Online:
- July 2019
- ISBN:
- 9780190945350
- eISBN:
- 9780190945381
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780190945350.003.0001
- Subject:
- Philosophy, Moral Philosophy

This chapter argues for the opting-for-the-best view: the view that, for any subject S and any member ϕ of a certain subset of S’s options, S ought to ϕ if and only if ϕ is the best member of this ... More

View:

- no detail
- some detail
- full detail