Monday, October 3, 2011

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).

No comments:

Post a Comment