ConceptTheory & Algos
Derandomization
The process of replacing random bits in an algorithm with pseudorandom strings generated deterministically from a short seed.
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.
Randomized algorithm5Deterministic algorithm3BPP1Complexity classes1Complexity classes like BPP and P1Expander graph1P/poly1Polynomial time1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
3Each in their own terms, from the easiest level.
Ryan O'Donnell
Venkatesan Guruswami
The process of removing randomness from an algorithm or complexity class, often replacing random bits with deterministic constructions or hardness assumptions.Seth Pettie
The process of converting a randomized algorithm into a deterministic algorithm that uses a magic function to simulate random bits from vertex IDs.
Lectures that assume it
1Connections
11The lectures that define it or assume it, and the concepts next to it.