[Busec] Fwd: PhD defense by Colin Zheng: Tuesday 7/23 at Harvard

Leonid Reyzin reyzin at cs.bu.edu
Thu Jul 18 17:54:13 EDT 2013

---------- Forwarded message ----------
From: "Vadhan, Salil P." <salil at seas.harvard.edu>
Date: Jul 18, 2013 12:02 PM
Subject: PhD defense by Colin Zheng: Tuesday 7/23
To: "theory-seminars at eecs.harvard.edu" <theory-seminars at eecs.harvard.edu>

Title: A Uniform Min-Max Theorem and Characterizations of Computational
Speaker: Colin Jia Zheng

Time:  Tuesday, July 23, 1:30-3pm
Place: Pierce 209

In the first half of the talk, I will present 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.  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.

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'' 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) > H(B|X), if
and only if there is no poly-sized circuit S that samples a distribution
S(X) ``close'' to B.  Using the Uniform Min-Max Theorem we also obtain
characterizations w.r.t. uniform algorithms S.

As an application of the characterization, letting H be the (Shannon)
entropy function provides a simple construction of ``next-bit
pseudoentropy'' 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.
Theory-seminars mailing list
Theory-seminars at eecs.harvard.edu
Subscribe/unsubscribe/customize at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20130718/27251306/attachment.html>

More information about the Busec mailing list