2008/01/18 by Fabrizio Altarelli, Altarelli, Fabrizio · 1 citation
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #Data Management and Algorithms #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Computer and information sciences #FOS: Physical sciences #Rough Sets and Fuzzy Logic #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.dis-nn #cond-mat.stat-mech #cs.CC
paper · pdf · doi:10.48550/arxiv.0801.2858
Ph.D. thesis, 132 pages
arxiv created 2008/01/18 · openalex publication_date 2008/01/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This thesis is divided in two parts. The first presents an overview of known results in statistical mechanics of disordered systems and its approach to random combinatorial optimization problems. The second part is a discussion of two original results. The first result concerns DPLL heuristics for random k-XORSAT, which is equivalent to the diluted Ising p-spin model. It is well known that DPLL is unable to find the ground states in the clustered phase of the problem, i.e. that it leads to contradictions with probability 1. However, no solid argument supports this is general. A class of heuristics, which includes the well known UC and GUC, is introduced and studied. It is shown that any heuristic in this class must fail if the clause to variable ratio is larger than some constant, which depends on the heuristic but is always smaller than the clustering threshold. The second result concerns the properties of random k-SAT at large clause to variable ratios. In this regime, it is well known that the uniform distribution of random instances is dominated by unsatisfiable instances. A general technique (based on the Replica method) to restrict the distribution to satisfiable instances with uniform weight is introduced, and is used to characterize their solutions. It is found that in the limit of large clause to variable ratios, the uniform distribution of satisfiable random k-SAT formulas is asymptotically equal to the much studied Planted distribution. Both results are already published and available as arXiv:0709.0367 and arXiv:cs/0609101 . A more detailed and self-contained derivation is presented here.