On the possibility of an instance-based complexity theory

…

Below some links related to the lecture’s coverage:

Computational complexity theory.
Minimum cut.
2-satisfiability.
3-SAT.
Worst-case complexity.
Average-case complexity.
Max-Cut.
Karp’s 21 NP-complete problems.
Reduction (complexity).
Levin’s Universal search algorithm – Scholarpedia.
Computational indistinguishability.
Circuit complexity.
Adversarial Perturbations of Deep Neural Networks.
Sherrington–Kirkpatrick model.
Equivalence class.
Hopkins (2018).
Planted clique.
SDP (Semidefinite programming).
Jain, Koehler & Risteski (2018): Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective.
Structural operational semantics (SOS).