All reports by Author Colin Jia Zheng:

__
TR13-101
| 12th July 2013
__

Colin Jia Zheng, Salil Vadhan#### A Uniform Min-Max Theorem with Applications in Cryptography

Revisions: 2

__
TR11-141
| 2nd November 2011
__

Salil Vadhan, Colin Jia Zheng#### Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

Revisions: 3

Colin Jia Zheng, Salil Vadhan

We present a new, more constructive proof of von Neumann's Min-Max Theorem for two-player zero-sum game --- specifically, an algorithm that builds a near-optimal mixed strategy for the second player from several best-responses of the second player to mixed strategies of the first player. The algorithm extends previous work of ... more >>>

Salil Vadhan, Colin Jia Zheng

We provide a characterization of pseudoentropy in terms of hardness of sampling: Let $(X,B)$ be jointly distributed random variables such that $B$ takes values in a polynomial-sized set. We show that $B$ is computationally indistinguishable from a random variable of higher Shannon entropy given $X$ if and only if there ... more >>>