Short & Clever Results

1. Katona's proof of Erdos-Ka-Rado theorem. [link]
2. Karger's randomized min-cut algorithm.[Notes]
3. Interactive Proof System.
4. Deffie-Hellman protocol.[link]
5. Dobkin and Lipton's lower bound proof of element distinctness problem.
6. Reflections on trust by Ken Thompson.[pdf]
7. Schöning's Algorithm for 3SAT.[pdf]
8. Perceptron algorithm for finding a separating plane.
9. Deradomization using an expander.(Linial's ppt)
10. Least Common Ancestor in O(1) time. (Erik Demaine notes).