2016/10/24 by Subhajit Goswami, Goswami, Subhajit
Biochemistry, Genetics and Molecular Biology · Computer Science · Decision Sciences · #60F99 #Constraint Satisfaction and Optimization #FOS: Mathematics #Probability (math.PR) #Scientific Computing and Data Management #Single-cell and spatial transcriptomics
paper · pdf · doi:10.48550/arxiv.1610.07431
openalex publication_date 2016/10/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a "configuration model" for random XORSAT which is a random system of n equations over m variables in \mathbb F2. Each equation is of the form y1 + y2 + ⋯ + yk = b where k ≥ 3 is fixed, y1, y2, ⋯ are variables (not necessarily distinct) and b ∈ \mathbb F2. The equations are chosen independently and uniformly at random with replacement. It is known \citeDubois02, Dietzfelbinger10, pittel2016 that there exists ρk such that m / n = ρk is a sharp threshold for the satisfiability of this system. In this note we show that for the configuration model, the width of SAT-UNSAT transition window for random k-XORSAT is Θ(n-1/2) and also derive the exact scaling function.