The Normalized Autocorrelation Length of Random Max $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$
From MaRDI portal
Publication:2818001
DOI10.1007/978-3-319-40970-2_5zbMath1478.68200OpenAlexW2467022100MaRDI QIDQ2818001
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
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
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$$