A Note On Psuedorandomness

• Home Page
• Biography
• PGP Public Key
• Research
• Writings
  • Grad School Advice
  • RoShamBo and Compression
  • The Two Envelope Problem
  • Two Envelope Variant
  • Statistical Learning Theory
  • The Coin Game Paradox
  • Quantum Mechanics
  • Analysis Of Multi-tasking
  • Note on Psuedorandomness
  • Note on Bit Commitment
• Source Code
• Pictures

During Fall 1999 I enrolled in a cryptography course at MIT taught by professor Silvio Micali. While lecturing on pseudorandom number generators, professor Micali challenged the class to prove a particular theorem about different kinds of polynomial unpredictability. A proof for his challenge is included below. You probably won't be intrested in it unless you took the same class.