A Uniform Min-Max Theorem and Characterizations of Computational Randomness

Vadhan, Salil P.Zheng, Jia2014-02-252014-02-252014Zheng, Jia. 2014. A Uniform Min-Max Theorem and Characterizations of Computational Randomness. Doctoral dissertation, Harvard University.http://dissertations.umi.com/gsas.harvard:11298http://nrs.harvard.edu/urn-3:HUL.InstRepos:11745716This thesis develops several tools and techniques using ideas from information theory, optimization, and online learning, and applies them to a number of highly related fundamental problems in complexity theory, pseudorandomness theory, and cryptography.en-USComputer scienceA Uniform Min-Max Theorem and Characterizations of Computational RandomnessThesis or Dissertation2014-02-25