Oct 27, 3:30pm, Wean 8220

Boris Pittel, Ohio State

On the satisfiability threshold for k-XORSAT

Boris Pittel, Ohio State

On the satisfiability threshold for k-XORSAT

Abstract:

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.