ConceptTheory & Algos
Random self-reducibility
A property where a problem can be solved in the worst case with high probability by reducing it to instances of the same problem on random inputs.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Lecturers
2Each in their own terms, from the easiest level.
Shafi Goldwasser
A property where solving a problem on a worst-case instance can be reduced to solving it on random instances drawn from a specific distribution and combining the solutions.
Connections
5The lectures that define it or assume it, and the concepts next to it.