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

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!

share|improve this question
    
Yes, we can.... –  slimton Oct 2 '11 at 7:51
1  
Please add your answer as an actual answer, so others can benefit. It is ok to answer your own question. –  David Roberts Oct 3 '11 at 3:59
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.