Séminaire du 30 novembre 2009, 10h30: Vlady
Ravelomanana, Université de Paris 13.
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)
Virginie Collette
Last modified: Mon Nov 23 14:23:53 CET 2009