The ACO Seminar (2011-2012)

We consider an "unconstrained" random k-XORSAT problem, which is a uniformly random system of m linear non-homogeneous Boolean equations over n variables, each equation containing k ≥ 3 variables, and a "constrained" model where every variable appears in at least two equations. For k = 3, Dubois and Mandler proved that m/n = 1 is a sharp threshold for almost certain solvability of constrained k-XORSAT. In this paper we prove that m/n = 1 remains a sharp threshold for solvability for every k ≥ 3, contingent on a conjecture of negativity of a certain function of k and two other variables. The conjecture is rigorously proved for the near-boundary values of the latter two arguments, and is firmly supported by numerical evidence for the interior values. Like Dubois-Mandler's method, our proof requires a study of a certain calculus of variations problem. A crucial difference is that the number of parameters in our approach is independent of k, while a direct extension of their technique would have led to a calculus of variations problem with a linearly increasing number of parameters. Dubois and Mandler used their result in conjunction with analysis of a reduction algorithm, (a 2-core algorithm for a random 3-regular hypergraph), to pinpoint the threshold value of m/n for the unconstrained 3-XORSAT problem. Using Molloy's analysis of the core of a random k-uniform hypergraph, we extend the Dubois-Mandler formula to unconstrained k-XORSAT for all k ≥ 3.

Joint work with Greg Sorkin.