* Optimal asymptotic time/space efficiencies for the most important problems
* The best known exponent for matrix multiplication
* Names and definitions of some popular complexity classes
* Some common but not obvious big/little O comparisons
* Dual conversions from optimization
* Probabilistic bounds used all over CS (Chernoff, Chebyshev)
* Basic facts about spectral graph theory
* The most often used inequalities like (1-x) < e^{-x} that follow from Taylor expansions
* Best known approximation ratios for various problems
* Central open conjectures like P vs NP and the unique games conjecture
* VC/margin bounds from learning theory
I could go on...
jkun, you have the honors?
* Optimal asymptotic time/space efficiencies for the most important problems
* The best known exponent for matrix multiplication
* Names and definitions of some popular complexity classes
* Some common but not obvious big/little O comparisons
* Dual conversions from optimization
* Probabilistic bounds used all over CS (Chernoff, Chebyshev)
* Basic facts about spectral graph theory
* The most often used inequalities like (1-x) < e^{-x} that follow from Taylor expansions
* Best known approximation ratios for various problems
* Central open conjectures like P vs NP and the unique games conjecture
* VC/margin bounds from learning theory
I could go on...