MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is the formal definition of Random Reducibility>

Arora/Barak is like:

"yeah, so it's kind like you take an instance of a problem, create n random instances of the problem; and if you have the solution to those n instanes; then in polynomial time you can solve your original instance."

doesn't seem much better -- giving examples rather than a rigorous definition.

What is the rigorous definition of random self-reducibility? [And why do people tend to give hand wavey definitions?]


share|cite|improve this question
Here is the definition from the Wikipedia article you have linked: "If a function $f$ evaluating any instance $x$ can be reduced in polynomial time to the evaluation of f on one or more random instances $y_i$, then it is self-reducible (this is also known as a non-adaptive uniform self-reduction)." – Kaveh Sep 7 '11 at 7:12
i.e. it is the same as self-reducibility, with the difference that instances in the self-reduction are chosen randomly. – Kaveh Sep 7 '11 at 7:13
You first speak about random reducibility, and then random self-reducibility. It is not the same thing! Though I think your question really is about self-reducibility. – Bruno Sep 7 '11 at 7:43
The Feigenbaum–Fortnow paper linked from the Wikipedia article ( has formal definitions on page 3. – Emil JeĹ™ábek Sep 7 '11 at 10:46

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.