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

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|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 (cs.uchicago.edu/~fortnow/papers/rsr.ps) 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.