Satisfiability thresholds beyond k-XORSAT

2011/12/09 by Andreas Goerdt, Goerdt, Andreas, Lutz Falke +1 · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.48550/arxiv.1112.2118

openalex publication_date 2011/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider random systems of equations x₁ + ... + x_k = a; 0 <= a <= 2 which are interpreted as equations modulo 3: We show for k >= 15 that the satisfiability threshold of such systems occurs where the 2-core has density 1: We show a similar result for random uniquely extendible constraints over 4 elements. Our results extend previous results of Dubois/Mandler for equations mod 2 and k = 3 and Connamacher/Molloy for uniquely extendible constraints over a domain of 4 elements with k = 3 arguments. Our proof technique is based on variance calculations, using a technique introduced Dubois/Mandler. However, several additional observations (of independent interest) are necessary.

Citations

• Tight Thresholds for Cuckoo Hashing via XORSAT

Cited by

• The satisfiability threshold and solution space of random uniquely extendable constraint satisfaction problems

Related

• The Satisfiability Threshold for k-XORSAT, using an alternative proof
• The Satisfiability Threshold for k-XORSAT
• The Satisfiability Threshold of Random 3-SAT Is at Least 3.52
• Approximating the satisfiability threshold for random k-XOR-formulas
• Proof of the satisfiability conjecture for large k