The replica symmetric phase of random constraint satisfaction problems
| Autor: | Noela Müller, Tobias Kapetanopoulos, Amin Coja-Oghlan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
Statistics and Probability Class (set theory) Theoretical computer science Discrete Mathematics (cs.DM) Contiguity 05C80 0102 computer and information sciences Bayesian inference 01 natural sciences Theoretical Computer Science Combinatorics FOS: Mathematics Mathematics - Combinatorics 0101 mathematics Constraint satisfaction problem Applied Mathematics Replica Probability (math.PR) 010102 general mathematics Probabilistic logic Satisfiability Computational Theory and Mathematics 010201 computation theory & mathematics Benchmark (computing) Combinatorics (math.CO) Mathematics - Probability Computer Science - Discrete Mathematics |
| Popis: | AbstarctRandom constraint satisfaction problems play an important role in computer science and combinatorics. For example, they provide challenging benchmark examples for algorithms, and they have been harnessed in probabilistic constructions of combinatorial structures with peculiar features. In an important contribution (Krzakala et al. 2007, Proc. Nat. Acad. Sci.), physicists made several predictions on the precise location and nature of phase transitions in random constraint satisfaction problems. Specifically, they predicted that their satisfiability thresholds are quite generally preceded by several other thresholds that have a substantial impact both combinatorially and computationally. These include the condensation phase transition, where long-range correlations between variables emerge, and the reconstruction threshold. In this paper we prove these physics predictions for a broad class of random constraint satisfaction problems. Additionally, we obtain contiguity results that have implications for Bayesian inference tasks, a subject that has received a great deal of interest recently (e.g. Banks et al. 2016, Proc. 29th COLT). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|