# Approximate Solving Linear Equations

EDIT: RESOLVED.

Given:

$$x, \{r_i\}_{i=1}^m \in \{0,1\}^n$$

$$\Pr_{i} [b_i = c \cdot x_i] \geq 1/2 + \epsilon$$

We are given: $$(b_i, r_i)$$

Question:

can we in polynomial time find an approximate solution, i.e. x' s.t.

$$\Pr_{i} x' \cdot r_i = b_i \geq 1/2 + \epsilon/2$$

m = poly in terms of n

Thanks!

-
Yes, we can.... –  slimton Oct 2 '11 at 7:51