Random 2-XOR-SAT and MAX-2-XOR-SAT and their phase transitions

We consider the $2$-XOR satisfiability problem, in which each instance is a formula that is a conjunction of Boolean equations of the form $x \oplus y= 0$ or $x \oplus y= 1$. Formula of size $m$ on $n$ Boolean variables are chosen uniformly at random from among all ${n(n-1)\choose m}$ possible choices. In the first part of this talk, we propose a complete picture of the finite size scaling associated to the subcritical and critical regions of SAT/UNSAT transition. In the second part of the talk, we consider the optimization version, known as MAX-2-XORSAT, of the previous decision problem. The MAX-2-XORSAT problem asks for the maximum number of clauses which can be satisfied by any assignment of the variables in a $2$-XOR formula. Let $X_{n,m}$ be the \textit{minimum} number of clauses that can not be satisfied in a formula with $n$ variables and $m$ clauses. We give precise characterizations of the random variable $X_{n,m}$ for $m = \Theta(n)$. The results describe phase transitions in the optimization context similar to those encountered in decision problems. (Joint work with Hervé Daudé and Vonjy Rasendrahasina)