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
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 coding/information theory. The topics which have been selected, including spin glasses, error correcting codes, satisfiability, are central to each field. The approach focuses on the limit of large random instances, adopting a common formulation in terms of graphical models. It presents message passing algorithms like belief propagation and survey propagation, and their use in decoding and constraint satisfaction solving. It also explains analysis techniques like density evolution and the cavity method, and uses them to derive phase diagrams and study phase transitions.Less
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 coding/information theory. The topics which have been selected, including spin glasses, error correcting codes, satisfiability, are central to each field. The approach focuses on the limit of large random instances, adopting a common formulation in terms of graphical models. It presents message passing algorithms like belief propagation and survey propagation, and their use in decoding and constraint satisfaction solving. It also explains analysis techniques like density evolution and the cavity method, and uses them to derive phase diagrams and study phase transitions.
Rolf Niedermeier
- 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
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 application problem from railway optimization, and concludes with a communication problem in tree networks (Multicut in Trees). It briefly summarizes the leitmotif of parameterized algorithm design and analysis.Less
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 application problem from railway optimization, and concludes with a communication problem in tree networks (Multicut in Trees). It briefly summarizes the leitmotif of parameterized algorithm design and analysis.
Marc Mézard and Andrea Montanari
- 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
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 instances. When the density of constraints is increased, a phase transition between a SAT and an UNSAT phase take place. Properly tuned ensembles with a density close to the transition point provide a generator of particularly hard instances. The nature of this transition is discussed, and bounds on the critical density are obtained. On the algorithmic side, the discussion focuses on exhaustive search algorithms based on tree-search, and on random walk procedures.Less
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 instances. When the density of constraints is increased, a phase transition between a SAT and an UNSAT phase take place. Properly tuned ensembles with a density close to the transition point provide a generator of particularly hard instances. The nature of this transition is discussed, and bounds on the critical density are obtained. On the algorithmic side, the discussion focuses on exhaustive search algorithms based on tree-search, and on random walk procedures.
Marc Mézard and Andrea Montanari
- 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
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 problems, from satisfiability to colouring or error correcting codes. This chapter describes a physics-based approach for dealing with such a problem, the ‘one step replica symmetry breaking’ (1RSB) cavity method. It is based on the idea of counting solutions to belief propagation equations, and has strong connections with the theory of pure states decomposition. Its algorithmic side, the survey propagation algorithm, is motivated and described in details. The general theory is illustrated through its application to the XORSAT problem studied in Chapter 18.Less
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 problems, from satisfiability to colouring or error correcting codes. This chapter describes a physics-based approach for dealing with such a problem, the ‘one step replica symmetry breaking’ (1RSB) cavity method. It is based on the idea of counting solutions to belief propagation equations, and has strong connections with the theory of pure states decomposition. Its algorithmic side, the survey propagation algorithm, is motivated and described in details. The general theory is illustrated through its application to the XORSAT problem studied in Chapter 18.
Marc Mézard and Andrea Montanari
- 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
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 particular the location of the SAT-UNSAT threshold. Within the SAT phase, the chapter focuses on the intermediate clustered phase close, and computes the number of clusters to leading exponential order in N. The application of survey propagation to this problem is then described. Combined with a simple decimation procedure, the chapter provides an efficient method for finding satisfiable assignments in the clustered phase. The whole chapter is based on heuristic arguments. There is not yet any rigorous proof of the results presented, neither concerning the phase diagram, nor the convergence properties of message passing algorithms and their use in decimation procedures.Less
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 particular the location of the SAT-UNSAT threshold. Within the SAT phase, the chapter focuses on the intermediate clustered phase close, and computes the number of clusters to leading exponential order in N. The application of survey propagation to this problem is then described. Combined with a simple decimation procedure, the chapter provides an efficient method for finding satisfiable assignments in the clustered phase. The whole chapter is based on heuristic arguments. There is not yet any rigorous proof of the results presented, neither concerning the phase diagram, nor the convergence properties of message passing algorithms and their use in decimation procedures.
Marc Mézard and Andrea Montanari
- 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
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 complexity, presenting the basic classes P, NP, and NP-complete. These notions are illustrated by discussions of the minimal spanning tree and satisfiability problems, and by applications from statistical physics (spin glasses and maximum cuts), and from coding theory (decoding complexity).Less
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 complexity, presenting the basic classes P, NP, and NP-complete. These notions are illustrated by discussions of the minimal spanning tree and satisfiability problems, and by applications from statistical physics (spin glasses and maximum cuts), and from coding theory (decoding complexity).
Hidetoshi Nishimori
- 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
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 are useful to study some types of optimization problems including the number partitioning, the graph partitioning, the knapsack problem, and the satisfiability problem. All these problems are shown to be formulated and solved using the theory of spin glasses, in particular the replica method. Then, discussions are continued on the mathematical properties of simulated annealing, an approximate numerical method for generic optimization problems.Less
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 are useful to study some types of optimization problems including the number partitioning, the graph partitioning, the knapsack problem, and the satisfiability problem. All these problems are shown to be formulated and solved using the theory of spin glasses, in particular the replica method. Then, discussions are continued on the mathematical properties of simulated annealing, an approximate numerical method for generic optimization problems.
Massimiliano Di Ventra
- 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
This Chapter introduces the Turing paradigm of computation and computational complexity classes. It discusses the algorithmic way combinatorial optimization problems are traditionally solved and explains why some of them are particularly difficult to solve with algorithms. It anticipates the need for non-perturbative approaches to the solution of such problems.Less
This Chapter introduces the Turing paradigm of computation and computational complexity classes. It discusses the algorithmic way combinatorial optimization problems are traditionally solved and explains why some of them are particularly difficult to solve with algorithms. It anticipates the need for non-perturbative approaches to the solution of such problems.
Massimiliano Di Ventra
- 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.
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.
Matthew Cook
- 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
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 objects of low period remain, providing a final density of about .0287. No methods are known for proving rigorously that this behavior should occur, but it is reliably observed in simulations. This brings up several interesting related questions. Why does this “freezing” occur? After everything has frozen, what is the remaining debris composed of? Is there some construction that can “eat through” the debris? If we start with an infinitely large random grid, so that all constructions appear somewhere, what will the long term behavior be? It seems clear that knowing the composition of typical debris is central to many such questions. Much effort has gone into analyzing the objects that occur in such stationary debris, as well as into determining what stationary objects can exist at all in Life [4, 8], Both of these endeavors depend on having some notion of what an “object” is in the first place. One simple notion is that of an island, a maximal set of live cells connected to each other by paths of purely live cells. But many common objects, such as the “aircraft carrier,” are not connected so strongly. They are composed of more than one island, but we think of them as a single object anyway, since their constituent islands are not separately stable. Any pattern that is stable (has period one, i.e., does not change over time) is called a still life. Since a collection of stable objects can satisfy this definition, the term strict still life is used to refer to a single indivisible stable object, and pseudo still life is used to refer to a stable pattern that is composed of distinct strict still lifes. For example, the bi-block is a pseudo still life, since it is composed of two blocks, but the aircraft carrier is a strict still life, since its islands are not stable on their own.
Less
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 objects of low period remain, providing a final density of about .0287. No methods are known for proving rigorously that this behavior should occur, but it is reliably observed in simulations. This brings up several interesting related questions. Why does this “freezing” occur? After everything has frozen, what is the remaining debris composed of? Is there some construction that can “eat through” the debris? If we start with an infinitely large random grid, so that all constructions appear somewhere, what will the long term behavior be? It seems clear that knowing the composition of typical debris is central to many such questions. Much effort has gone into analyzing the objects that occur in such stationary debris, as well as into determining what stationary objects can exist at all in Life [4, 8], Both of these endeavors depend on having some notion of what an “object” is in the first place. One simple notion is that of an island, a maximal set of live cells connected to each other by paths of purely live cells. But many common objects, such as the “aircraft carrier,” are not connected so strongly. They are composed of more than one island, but we think of them as a single object anyway, since their constituent islands are not separately stable. Any pattern that is stable (has period one, i.e., does not change over time) is called a still life. Since a collection of stable objects can satisfy this definition, the term strict still life is used to refer to a single indivisible stable object, and pseudo still life is used to refer to a stable pattern that is composed of distinct strict still lifes. For example, the bi-block is a pseudo still life, since it is composed of two blocks, but the aircraft carrier is a strict still life, since its islands are not stable on their own.
Douglas W. Portmore
- 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
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 subset in terms of whatever ultimately matters. It’s argued that we need to restrict ourselves to a subset of the subject’s options because of the problem of act versions. This problem arises in the following sort of case. One’s best option is to kiss one’s partner passionately. Kissing her nonpassionately would be disastrous. Indeed, it would be better not to kiss her at all. But, unfortunately, if you were to kiss her, you would do so nonpassionately. Should you kiss her? Of course, you have to kiss her to kiss her passionately, which is your best option. But kissing her would result in your kissing her nonpassionately, which is your worst option.Less
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 subset in terms of whatever ultimately matters. It’s argued that we need to restrict ourselves to a subset of the subject’s options because of the problem of act versions. This problem arises in the following sort of case. One’s best option is to kiss one’s partner passionately. Kissing her nonpassionately would be disastrous. Indeed, it would be better not to kiss her at all. But, unfortunately, if you were to kiss her, you would do so nonpassionately. Should you kiss her? Of course, you have to kiss her to kiss her passionately, which is your best option. But kissing her would result in your kissing her nonpassionately, which is your worst option.