<div class="gmail_quote">---------- Forwarded message ----------<br>From: &quot;Vadhan, Salil P.&quot; &lt;<a href="mailto:salil@seas.harvard.edu">salil@seas.harvard.edu</a>&gt;<br>Date: Jul 18, 2013 12:02 PM<br>Subject: PhD defense by Colin Zheng: Tuesday 7/23<br>
To: &quot;<a href="mailto:theory-seminars@eecs.harvard.edu">theory-seminars@eecs.harvard.edu</a>&quot; &lt;<a href="mailto:theory-seminars@eecs.harvard.edu">theory-seminars@eecs.harvard.edu</a>&gt;<br>Cc: <br><br type="attribution">
<br>
Title: A Uniform Min-Max Theorem and Characterizations of Computational Randomness<br>
Speaker: Colin Jia Zheng<br>
<br>
Time:  Tuesday, July 23, 1:30-3pm<br>
Place: Pierce 209<br>
<br>
Abstract:<br>
In the first half of the talk, I will present a new, more constructive proof of von Neumann&#39;s Min-Max Theorem for two-player zero-sum game, extending previous work of Freund and Schapire.  This extension 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 with optimal parameters.  I will describe several of the applications.<br>

<br>
In the second half, I will show a new characterization of notions of computational randomness in terms of notions of computational hardness.  Given any ``nice&#39;&#39; function H on distributions (e.g. the entropy function), and 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 H(C|X) &gt; H(B|X), if and only if there is no poly-sized circuit S that samples a distribution S(X) ``close&#39;&#39; to B.  Using the Uniform Min-Max Theorem we also obtain characterizations w.r.t. uniform algorithms S.<br>

<br>
As an application of the characterization, letting H be the (Shannon) entropy function provides a simple construction of ``next-bit pseudoentropy&#39;&#39; from one-way functions.  Plugging this into the construction of pseudorandom generators by Haitner, Reingold, and Vadhan, 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 Haitner et al.<br>

_______________________________________________<br>
Theory-seminars mailing list<br>
<a href="mailto:Theory-seminars@eecs.harvard.edu">Theory-seminars@eecs.harvard.edu</a><br>
Subscribe/unsubscribe/customize at <a href="https://lists.eecs.harvard.edu/mailman/listinfo/theory-seminars" target="_blank">https://lists.eecs.harvard.edu/mailman/listinfo/theory-seminars</a><br>
</div>