2003/08/25 by Giorgio Parisi, Parisi, Giorgio · 1 citation
Computer Science · Engineering · Physics and Astronomy · #Algorithms and Data Compression #Disordered Systems and Neural Networks (cond-mat.dis-nn) #Error Correcting Code Techniques #FOS: Physical sciences #Statistical Mechanics (cond-mat.stat-mech) #Underwater Vehicles and Communication Systems #cond-mat.dis-nn #cond-mat.stat-mech
paper · pdf · doi:10.48550/arxiv.cond-mat/0308510
9 pages, two figures
arxiv created 2003/08/25 · openalex publication_date 2003/08/25 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we present a backtracking version of the survey propagation algorithm. We show that the introduction of the simplest form of backtracking greatly improves the ability of the original survey propagation algorithm in solving difficult random problems near the sat-unsat transition.