Symmetric Rule-Based Achlioptas Processes for Random k-SAT

2025/10/09 by Arnab Chatterjee, Chatterjee, Arnab
Computer Science · #Constraint Satisfaction and Optimization #Distributed systems and fault tolerance #Formal Methods in Verification

paper · pdf · doi:10.48550/arxiv.2510.07870

Abstract

Inspired by the "power-of-two-choices" model from random graphs, we investigate the possibility of limited choices of online clause choices that could shift the satisfiability threshold in random k-SAT.Here, we introduce an assignment symmetric, non-adaptive, topology-oblivious online rule called MIDDLE-HEAVY, that prioritizes balanced sign profile clauses.Upon applying a biased 2-SAT projection and a two-type branching process certificate, we derive closed-form expressions for the shifted thresholds α_SYM(k,ℓ) for this algorithm.We show that minimal choices ℓ=5 for k=4, ℓ=4 for k=5, and ℓ=3 for k≥ 6 suffice to exceed the asymptotic first-moment upper bound ∼ 2^k ln 2 for random k-SAT.Moreover, to bridge the gap with biased assignment rules used in maximum of the previous works in this context, we propose a hybrid symmetric biased rule that achieves thresholds comparable to prior work while maintaining symmetry.Our results advance the understanding of Achlioptas processes in random CSPs beyond classical graph-theoretic settings.

Citations

• Belief Propagation Guided Decimation on Random k-XORSAT
• The number of random 2-SAT solutions is asymptotically log-normal
• Proof of the satisfiability conjecture for large k
• The Power of Choice for Random Satisfiability
• Random k-SAT and the Power of Two Choices
• Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold

Related

• Random k-SAT and the Power of Two Choices
• The Power of Choice for Random Satisfiability
• Random MAX SAT, Random MAX CUT, and Their Phase Transitions
• The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
• Biased random k-SAT