ConceptTheory & Algos
Average-case hardness
The property that circuits of a given size are wrong on almost all inputs, performing as badly as random guessing.
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.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
2Each in their own terms, from the easiest level.
Ryan O'Donnell
Average-case hardness asks whether there exists a fixed hard instance generator that can fool any polynomial time algorithm with high probability.
Lectures that assume it
1Connections
7The lectures that define it or assume it, and the concepts next to it.