Message passing algorithms for MLS-3LIN problem

DOI10.1007/S00453-013-9762-7zbMath1311.68152OpenAlexW1997920878MaRDI QIDQ378230

Osamu Watanabe

Publication date: 11 November 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9762-7

zbMATH Keywords

spectral analysismessage passing algorithmMAX-3XORSATplanted solution model

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
• Average-case analysis for the MAX-2SAT problem
• A spectral heuristic for bisecting random graphs
• A Spectral Approach to Analysing Belief Propagation for 3-Colouring
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Spectral techniques applied to sparse random graphs
• A Simple Message Passing Algorithm for Graph Partitioning Problems
• Propagation Connectivity of Random Hypergraphs
• Propagation Connectivity of Random Hypergraphs

This page was built for publication: Message passing algorithms for MLS-3LIN problem