Computer Science – Discrete Mathematics
Scientific paper
2011-07-27
Computer Science
Discrete Mathematics
51 pages
Scientific paper
The XOR-satisfiability (XORSAT) problem requires finding an assignment of n Boolean variables that satisfies m exclusive OR (XOR) clauses, whereby each clause constrains a subset of the variables. We consider random XORSAT instances, drawn uniformly at random from the ensemble of formulae containing n variables and m clauses of size k. This model presents several structural similarities to other ensembles of constraint satisfaction problems, such as k-satisfiability (k-SAT). For many of these ensembles, as the number of constraints per variable grows, the set of solutions shatters into an exponential number of well-separated components. This phenomenon appears to be related to the difficulty of solving random instances of such problems. We prove a complete characterization of this clustering phase transition for random k-XORSAT. In particular we prove that the clustering threshold is sharp and determine its exact location. We prove that the set of solutions has large conductance below this threshold and that each of the clusters has large conductance above the same threshold. Our proof constructs a very sparse basis for the set of solutions (or the subset within a cluster). This construction is achieved through a low complexity iterative algorithm.
Ibrahimi Morteza
Kanoria Yashodhan
Kraning Matt
Montanari Andrea
No associations
LandOfFree
The Set of Solutions of Random XORSAT Formulae does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Set of Solutions of Random XORSAT Formulae, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Set of Solutions of Random XORSAT Formulae will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-112649