Index of results

50 of 100 written, from 110 entry lines.

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