The Normalized Autocorrelation Length of Random Max $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$

DOI10.1007/978-3-319-40970-2_5zbMath1478.68200OpenAlexW2467022100MaRDI QIDQ2818001

Daniel Berend, Yochai Twitto

Publication date: 5 September 2016

Published in: Theory and Applications of Satisfiability Testing – SAT 2016 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-40970-2_5

zbMATH Keywords

combinatorial optimizationlocal searchfitness landscapesautocorrelation lengthMax Sat

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational aspects of satisfiability (68R07)

Related Items (2)

Probabilistic characterization of random Max \(r\)-Sat ⋮ Using the method of conditional expectations to supply an improved starting point for CCLS

Uses Software

• UBCSAT
• Walksat
• MaxHS
• CCLS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• SAT-based MaxSAT algorithms
• Autocorrelation measures for the quadratic assignment problem
• Autocorrelation coefficient for the graph bipartitioning problem
• Exploiting the deep structure of constraint problems
• On the classification of NP-complete problems in terms of their correlation coefficient
• A tutorial on the cross-entropy method
• CCLS: An Efficient Local Search Algorithm for Weighted Maximum Satisfiability
• Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
• Sharp thresholds of graph properties, and the $k$-sat problem
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The asymptotic k-SAT threshold
• Threshold values of random K‐SAT from the cavity method
• Theory and Applications of Satisfiability Testing
• On the landscape ruggedness of the quadratic assignment problem

This page was built for publication: The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$