Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


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


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.