Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains

DOI10.1088/1742-5468/abe6fezbMath1504.68206OpenAlexW3138257960MaRDI QIDQ4992313

Chunyan Zhao, Yan-Rong Fu

Publication date: 8 June 2021

Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1088/1742-5468/abe6fe

zbMATH Keywords

analysis of algorithmsheuristic algorithmsbelief propagationmessage-passing algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (1)

Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length

Cites Work

• Unnamed Item
• Unnamed Item
• On the phase transitions of random \(k\)-constraint satisfaction problems
• Local search with edge weighting and configuration checking heuristics for minimum vertex cover
• The SAT-UNSAT transition for random constraint satisfaction problems
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• A probabilistic analysis of randomly generated binary constraint satisfaction problems.
• Threshold behaviors of a random constraint satisfaction problem with exact phase transitions
• On the constraint length of random \(k\)-CSP
• Many hard examples in exact phase transitions
• An empirical study of phase transitions in binary constraint satisfaction problems
• Locating the phase transition in binary constraint satisfaction problems
• Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
• Information, Physics, and Computation
• Factor graphs and the sum-product algorithm
• The capacity of low-density parity-check codes under message-passing decoding
• Models for Random Constraint Satisfaction Problems
• Biased landscapes for random constraint satisfaction problems
• Two faces of greedy leaf removal procedure on graphs
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• Random constraint satisfaction: A more accurate picture
• Random constraint satisfaction: Flaws and structure
• Statistical mechanics methods and phase transitions in optimization problems
• Constructing an asymptotic phase transition in random binary constraint satisfaction problems
• Bounding the scaling window of random constraint satisfaction problems

This page was built for publication: Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains