Algorithm for testing satisfiable fraction of linear equations mod 2

2011-04-25T04:48:48Z

Hello

Let $F_{n,p}$ be a random process which generates a system of linear equations over $F_2$. The variables are ${x_1, ..., x_n}$ and for each of the $ \binom{n}{2}$ $i,j$ pairs, the equation $x_i + x_j = b_{ij}$ gets generated with probability p, where $b_{ij}$ is chosen uniformly at random in $F_2$ too.

let $\phi$ be such a system of equations und let $OPT(\phi)$ denote the maximal fraction of satisfiable equations.

Given a constant $0 < \epsilon < 10^{-4}$

I would like to come up with a deterministic polytime algorithm A, and a constant $c > 0$ such that A:

accepts, if $OPT(\phi ) >= 1-\epsilon$
rejects with high probability, if $\phi \in F_{n, c/n }$

My problem is that the algorithm is not allowed to (wrongly) reject any $1-\epsilon$ satisfiable $\phi$.

My observation is that some subformula is unsatisfiable if, the subformula forms a cycle (when formulated as a graph) and a odd number of $b_{ij}$ equals 0.

But i have no idea how to chose the c.

Algorithm for testing satisfiable fraction of linear equations mod 2 - MathOverflow

Algorithm for testing satisfiable fraction of linear equations mod 2