Random self-reducibility
Random self-reducibility (RSR) is the rule that a good algorithm for the average case implies a good algorithm for the worst case. RSR is the ability to solve all instances of a problem by solving a large fraction of the instances.
From Wikipedia, the free encyclopedia Random self-reducibility (RSR) is the rule that a good algorithm for the average case implies a good algorithm for the worst case. RSR is the ability to solve all instances of a problem by solving a large fraction of the instances. If for a function f evaluating any instance x can be reduced in polynomial time to the evaluation of f on one or more random instances yi, then it is self-reducible (this is also known as a non-adaptive uniform self-reduction). In a random self-reduction, an arbitrary worst-case instance x in the domain of f is mapped to a…
saved by
related reading
- Computational Complexity Theory (Stanford Encyclopedia of Philosophy)plato.stanford.edu
- Secure multi-party computation - Wikipediaen.wikipedia.org
- Impagliazzo's Five Worldsblog.computationalcomplexity.org
- Computer Scientists Figure Out How To Prove Lies | Quanta Magazinequantamagazine.org
- ProofsArgsAndZK.pdfpeople.cs.georgetown.edu
- The Power of Noise — LessWronglesswrong.com
- What's new | Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Taoterrytao.wordpress.com
- Shtetl-Optimized >> Blog Archive >> Ten Signs a Claimed Mathematical Breakthrough is Wrongscottaaronson.blog
- Avi Wigderson, Complexity Theory Pioneer, Wins Turing Award | Quanta Magazinequantamagazine.org
- Pseudorandom generator - Wikipediaen.wikipedia.org
- CSE290A - Randomized Algorithmsusers.soe.ucsc.edu
- An intensive introduction to cryptography: indexintensecrypto.org