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.
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.
