@conference {634150,
	title = {A uniform min-max theorem with applications in cryptography},
	booktitle = {Ran Canetti and Juan Garay, editors, Advances in Cryptology{\textemdash}CRYPTO {\textquoteleft}13, Lecture Notes on Computer Science},
	volume = {8042},
	year = {2013},
	pages = {93-110},
	publisher = {Springer Verlag, Lecture Notes in Computer Science},
	organization = {Springer Verlag, Lecture Notes in Computer Science},
	abstract = {
	Version History:\&nbsp;



	Full version\&nbsp;published on\&nbsp;ECCC2013\&nbsp;and\&nbsp;IACR ePrint\&nbsp;2013.



	We present a new, more constructive proof of von Neumann{\textquoteright}s Min-Max Theorem for two-player zero-sum game {\textemdash} 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 Freund and Schapire (Games and Economic Behavior {\textquoteright}99) with the advantage that the algorithm runs in poly\((n)\) time even when a pure strategy for the first player is a distribution chosen from a set of distributions over\&nbsp;\(\{0,1\}^n\). This extension enables a number of additional 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).



	We describe several applications, including a more modular and improved uniform version of Impagliazzo{\textquoteright}s Hardcore Theorem (FOCS {\textquoteright}95), showing impossibility of constructing succinct non-interactive arguments (SNARGs) via black-box reductions under uniform hardness assumptions (using techniques from Gentry and Wichs (STOC {\textquoteright}11) for the nonuniform setting), and efficiently simulating high entropy distributions within any sufficiently nice convex set (extending a result of Trevisan, Tulsiani and Vadhan (CCC {\textquoteright}09)).

},
	url = {https://link.springer.com/chapter/10.1007/978-3-642-40041-4_6},
	author = {Salil Vadhan and Colin Jia Zheng}
}
