Take the 2-minute tour ×


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.

share|improve this question
i think the key observation is that the equations are randomly generated => the underlying (implication) graph is random and random graphs are have expander property. And the label covering problem (which the linear equation correspond to, i.e. unique game) is not hard on expanders. but still i have no idea how not to wrongly reject any 1-eps sat formula. –  user695652 Apr 26 '11 at 6:29

Your Answer



Browse other questions tagged or ask your own question.