2013/03/03 by S. Hamed Hassani, Hassani, S. Hamed, Nicolas Macris +3
Computer Science · Mathematics · Physics and Astronomy · #Discrete Mathematics (cs.DM) #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #cond-mat.dis-nn #cs.DM #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1303.0540
Submitted to ISIT 2013
arxiv created 2013/03/03 · arxiv updated 2013/03/05
The XOR-satisfiability (XORSAT) problem deals with a system of n Boolean variables and m clauses. Each clause is a linear Boolean equation (XOR) of a subset of the variables. A K-clause is a clause involving K distinct variables. In the random K-XORSAT problem a formula is created by choosing m K-clauses uniformly at random from the set of all possible clauses on n variables. The set of solutions of a random formula exhibits various geometrical transitions as the ratio (m)/(n) varies. We consider a \em coupled K-XORSAT ensemble, consisting of a chain of random XORSAT models that are spatially coupled across a finite window along the chain direction. We observe that the threshold saturation phenomenon takes place for this ensemble and we characterize various properties of the space of solutions of such coupled formulae.