A uniform min-max theorem and characterizations of computational randomness.

摘要

This 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. First, we give a new, more constructive proof of von Neumann's Min-Max Theorem for two-player zero-sum game, extending previous work of Freund and Schapire (Games and Economic Behavior `99). The resulting Uniform Min-Max Theorem enables a number of applications in cryptography and complexity theory, often yielding uniform security versions of results that were previously only proved for nonuniform security (due to use of the non-constructive Min-Max Theorem), and often with optimal parameters. We then develop several applications of the Uniform Min-Max Theorem, including: Regularity Theorems that provide efficient simulation of distributions within any sufficiently nice convex set; an improved version of the Weak Regularity Lemma for graphs; a simple and more modular uniform version of the Hardcore Theorem for boolean circuits; Dense Model Theorems for uniform algorithms; and impossibility of constructing Succinct Non-Interactive Arguments (SNARGs) via black-box reductions under uniform hardness assumptions. Next, we provide a new characterization of computational Shannon-entropy, in terms of the hardness of sampling a distribution. Given any joint distribution (X,B) where B takes values in a polynomial-sized set, we show that (X,B) is computationally indistinguishable to some joint distribution (X,C) with ;3);4)