2
$\begingroup$

I am given an oracle $A$ that takes input samples from two distributions $\chi_1$ and $\chi_2$.

Suppose we have $Pr_{x \sim \chi_1}[A(x) = 1] = p_1$ and $Pr_{x \sim \chi_2}[A(x) = 1] = p_2$, where $p_1 \neq p_2$.

In general, how can we use $A$ to construct a distinguisher to determine whether the input samples are from $\chi_1$ or $\chi_2$? And how good is the running time of such distinguisher?

Thank you very much! :)

$\endgroup$
2
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? Do you expect us to solve your question for you? $\endgroup$ May 5, 2013 at 5:16
  • 2
    $\begingroup$ Cross-posted on cstheory: cstheory.stackexchange.com/questions/17518/…. Don't do that. Your question there will be closed. $\endgroup$ May 5, 2013 at 5:18

1 Answer 1

1
$\begingroup$

Hint: Run $A$ on lots of samples $x_1,\ldots,x_n$ and compute the average $(A(x_1)+\cdots+A(x_n))/n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.