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 Neumanns 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 $HC|X) geq HB|X)＋delta$,if and only if there is no poly-sized circuit S such that the KL divergence from B to SX) is smaller than $delta$. We then use this characterization to show that if f is a one-way function,then $fU_n),U_n)$ has "next-bit pseudoentropy" at least n＋log n,establishing a conjecture of Haitner,Reingold,and Vadhan STOC `10). Plugging this into the construction of Haitner et al.,this yields a simpler construction of pseudorandom generators from one-way functions. With an additional idea,we also show how to improve the seed length of the pseudorandom generator to $tilde{O}n. 3)$,compared to $tilde{O}n. 4)$ in the construction of Haitneret al. In addition,this characterization establishes a connection to prediction markets based on market scoring rules. We also provide a new characterization of pseudo-avg-min-entropy,generalizing the Hardcore Theorem to polynomial-sized rather than binary) alphabets. The Uniform Min-Max Theorem is used to obtain uniform versions of both characterizations.