| Part I
Counting and Averaging Arguments |
T001 | Pigeonhole principle | theorem | Easy | #combinatorics#algorithms |
T002 | Cantor's diagonal argument | theorem | Easy | #logic#computability |
T003 | The Omega(n log n) comparison-sort bound | theorem | Medium | #algorithms#combinatorics |
T004 | No universal lossless compressor | theorem | Easy | #information-theory#combinatorics |
T005 | Adversary arguments | theorem | Medium | #algorithms#combinatorics |
T007 | Linearity of expectation | theorem | Easy | #probability#algorithms |
T008 | Concentration bounds (Chernoff/Hoeffding) | theorem | Medium | #probability#algorithms |
T074 | The birthday bound | theorem | Easy | #cryptography#probability#data-structures |
| Part II
Self-Reference and the Limits of Computation |
T010 | The Halting problem | theorem | Easy | #computability#logic |
T011 | Rice's theorem | theorem | Medium | #computability#pl-theory#security |
T012 | The Church–Turing thesis | thesis | Easy | #computability |
T013 | The universal machine | theorem | Easy | #computability#hardware |
T014 | Kleene's recursion theorem | theorem | Medium | #computability#logic |
T015 | Godel's incompleteness theorems | theorem | Medium | #logic |
T017 | Reductions | theorem | Medium | #computability#complexity |
| Part III
Information and Randomness |
T018 | Shannon entropy and the source coding theorem | theorem | Medium | #information-theory |
T020 | Huffman coding is optimal | theorem | Medium | #information-theory#algorithms |
T021 | The noisy-channel coding theorem | theorem | Hard | #information-theory#networking |
T022 | The Hamming bound and error-correcting codes | theorem | Medium | #information-theory#hardware |
T023 | Kolmogorov complexity | theorem | Medium | #information-theory#computability#probability |
T025 | Minimum description length and Occam's razor | theorem principle | Medium | #information-theory#machine-learning |
T106 | The Nyquist–Shannon sampling theorem | theorem | Medium | #information-theory#hardware |
T110 | The no-cloning theorem | physical-law | Medium | #hardware#information-theory#cryptography |
| Part IV
Complexity: Hard, and Provably So |
T026 | P vs NP | open-problem | Easy | #complexity |
T027 | The Cook–Levin theorem | theorem | Medium | #complexity#logic |
T028 | Karp's 21 problems | theorem | Medium | #complexity#algorithms |
T030 | The barriers: relativization and natural proofs | theorem | Hard | #complexity#logic |
T031 | The PCP theorem and inapproximability | theorem | Hard | #complexity |
T032 | Approximation algorithms and ratios | theorem | Medium | #complexity#algorithms#optimization |
T033 | Parameterized complexity (FPT and W[1]) | theorem | Medium | #complexity#algorithms |
T034 | Parity is not in AC^0 | theorem | Hard | #complexity#hardware |
T035 | BPP, pseudorandomness, and derandomization | theorem | Hard | #complexity#probability |
T036 | IP = PSPACE | theorem | Hard | #complexity#cryptography |
T037 | The Exponential Time Hypothesis and fine-grained complexity | conjecture | Medium | #complexity#algorithms |
| Part V
Languages, Logic, and Types |
T038 | The Chomsky hierarchy | theorem | Easy | #automata#compilers |
T039 | Kleene's theorem: regexes are finite automata | theorem | Medium | #automata#compilers |
T040 | The Myhill–Nerode theorem | theorem | Medium | #automata |
T041 | The lambda calculus and the Y combinator | theorem | Medium | #pl-theory#computability |
T042 | The Curry–Howard correspondence | theorem | Medium | #type-theory#logic#pl-theory |
T043 | Hindley–Milner and principal types | theorem | Medium | #type-theory#pl-theory |
T044 | Progress and preservation | theorem | Medium | #type-theory#formal-methods |
T045 | Parametricity: theorems for free | theorem | Medium | #type-theory#pl-theory |
T047 | Abstract interpretation and Galois connections | theorem | Hard | #formal-methods#compilers#pl-theory |
T048 | Hoare logic and weakest preconditions | theorem | Medium | #formal-methods#logic |
T049 | Model checking, LTL, and Buchi automata | theorem | Hard | #formal-methods#concurrency#automata |
T107 | Register allocation is graph coloring | theorem | Medium | #compilers#complexity#algorithms |
T050 | Resolution and CDCL | theorem empirical | Medium | #logic#algorithms#formal-methods |
| Part VI
Concurrency |
T051 | The Coffman conditions | theorem | Easy | #concurrency#operating-systems |
T109 | Work stealing and fair scheduling | theorem | Medium | #concurrency#performance#algorithms |
T052 | Mutual exclusion without hardware support | demonstration theorem | Medium | #concurrency#operating-systems |
T053 | Herlihy's wait-free consensus hierarchy | theorem | Hard | #concurrency#hardware |
T055 | Linearizability | theorem | Medium | #concurrency#distributed-systems |
T056 | Memory models and sequential consistency | theorem | Medium | #concurrency#hardware#compilers |
| Part VII
Distributed Systems |
T058 | Happens-before and Lamport clocks | theorem | Easy | #distributed-systems |
T059 | Vector clocks and causal consistency | theorem | Medium | #distributed-systems |
T061 | The Two Generals problem | theorem | Easy | #distributed-systems#networking |
T062 | FLP impossibility | theorem | Hard | #distributed-systems |
T063 | The Byzantine generals problem | theorem | Medium | #distributed-systems#security |
T064 | Paxos, Raft, and the shape of consensus | demonstration theorem | Medium | #distributed-systems#databases |
T065 | Quorum intersection (R + W > N) | theorem | Easy | #distributed-systems#databases |
T066 | The CAP theorem and PACELC | theorem | Medium | #distributed-systems#systems-design |
T067 | The CALM theorem and CRDTs | theorem | Hard | #distributed-systems#pl-theory |
| Part VIII
Data and Storage |
T069 | Codd's theorem | theorem | Medium | #databases |
T071 | Conflict serializability and two-phase locking | theorem | Medium | #databases#concurrency |
T009 | Balls into bins and the power of two choices | theorem | Medium | #probability#distributed-systems#performance |
T104 | Universal hashing | demonstration theorem | Medium | #data-structures#probability#algorithms |
T072 | Consistent hashing | demonstration theorem | Easy | #distributed-systems#data-structures |
T073 | Bloom filters | demonstration theorem | Easy | #data-structures#probability |
T105 | Streaming lower bounds and sketching | theorem | Medium | #information-theory#data-structures#algorithms |
| Part IX
Security and Cryptography |
T075 | Kerckhoffs's principle and perfect secrecy | principle theorem | Medium | #cryptography#security |
T076 | One-way functions and trapdoors | conjecture | Medium | #cryptography#complexity |
T077 | Zero-knowledge proofs | demonstration theorem | Hard | #cryptography#complexity |
T078 | Merkle trees | demonstration theorem | Easy | #cryptography#data-structures |
T079 | Reflections on Trusting Trust | demonstration | Medium | #security#compilers |
T080 | Saltzer and Schroeder's principles | principle | Easy | #security#systems-design |
| Part X
Systems, Performance, and Practice |
T081 | Amdahl's law | theorem | Easy | #performance#concurrency |
T082 | Gustafson's law and the Universal Scalability Law | empirical theorem | Medium | #performance#distributed-systems |
T083 | Little's law | theorem | Easy | #performance#systems-design |
T084 | Latency under utilization | theorem | Medium | #performance#systems-design |
T108 | Token buckets, arrival curves, and network calculus | theorem | Medium | #networking#performance#systems-design |
T006 | Amortized analysis and the potential method | theorem | Medium | #algorithms#data-structures |
T086 | Competitive analysis and ski rental | theorem | Easy | #algorithms#systems-design |
T085 | Belady's optimal algorithm and LRU competitiveness | theorem | Medium | #operating-systems#algorithms#performance |
T087 | The end-to-end argument | principle | Easy | #networking#systems-design |
T088 | Memory hierarchy and locality | empirical theorem | Medium | #performance#hardware#operating-systems#algorithms |
T089 | Conway's law | empirical | Easy | #software-engineering#systems-design |
T090 | No Silver Bullet and Brooks's law | empirical | Easy | #software-engineering |
T091 | Hyrum's law and Postel's principle | empirical principle | Easy | #software-engineering#networking#systems-design |
| Part XI
Optimization and Mechanism Design |
T092 | Max-flow min-cut | theorem | Medium | #optimization#algorithms |
T093 | LP duality | theorem | Medium | #optimization |
T094 | Matroids and greedy optimality | theorem | Hard | #algorithms#optimization |
T095 | Gale–Shapley stable matching | theorem demonstration | Easy | #optimization#algorithms |
T101 | Arrow's impossibility theorem | theorem | Medium | #optimization#systems-design |
| Part XII
Learning |
T096 | PAC learning and VC dimension | theorem | Hard | #machine-learning |
T097 | The bias–variance decomposition | theorem | Medium | #machine-learning |
T098 | No Free Lunch | theorem | Medium | #machine-learning |
T099 | Why the generalization bounds are vacuous | empirical theorem | Medium | #machine-learning |
T100 | The Johnson–Lindenstrauss lemma | theorem | Medium | #machine-learning#probability#data-structures |
| Part XIII
Physical Limits |
T102 | Landauer's principle | physical-law | Medium | #information-theory#hardware |
T103 | Shor and Grover: what quantum actually buys | theorem | Hard | #hardware#cryptography#complexity |