ECCC-Report TR13-101https://eccc.weizmann.ac.il/report/2013/101Comments and Revisions published for TR13-101en-usTue, 16 Jul 2013 01:41:28 +0300
Revision 2
| A Uniform Min-Max Theorem with Applications in Cryptography |
Salil Vadhan,
Colin Jia Zheng
https://eccc.weizmann.ac.il/report/2013/101#revision2We 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 Freund and Schapire (Games and Economic Behavior '99) with the advantage that the algorithm runs in $\mathrm{poly}(n)$ time even when a pure strategy for the first player is a distribution chosen from a set of distributions over $\{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's Hardcore Theorem (FOCS '95); regularity theorems that provide efficient simulation of distributions within any sufficiently nice convex set (extending a result of Trevisan, Tulsiani and Vadhan (CCC '09)); an improved version of the Weak Regularity Lemma of Frieze and Kannan; a Dense Model Theorem for uniform algorithms; and showing impossibility of constructing Succinct Non-Interactive Arguments (SNARGs) via black-box reductions under uniform hardness assumptions (using techniques from Gentry and Wichs (STOC '11) for the nonuniform setting).Tue, 16 Jul 2013 01:41:28 +0300https://eccc.weizmann.ac.il/report/2013/101#revision2
Revision 1
| A Uniform Min-Max Theorem with Applications in Cryptography |
Salil Vadhan,
Colin Jia Zheng
https://eccc.weizmann.ac.il/report/2013/101#revision1We 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 Freund and Schapire (Games and Economic Behavior '99) with the advantage that the algorithm runs in $\mathrm{poly}(n)$ time even when a pure strategy for the first player is a distribution chosen from a set of distributions over $\{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's Hardcore Theorem (FOCS '95); regularity theorems that provide efficient simulation of distributions within any sufficiently nice convex set (extending a result of Trevisan, Tulsiani and Vadhan (CCC '09)); an improved version of the Weak Regularity Lemma of Frieze and Kannan; a Dense Model Theorem for uniform algorithms; and showing impossibility of constructing Succinct Non-Interactive Arguments (SNARGs) via black-box reductions under uniform hardness assumptions (using techniques from Gentry and Wichs (STOC '11) for the nonuniform setting).Tue, 16 Jul 2013 01:34:41 +0300https://eccc.weizmann.ac.il/report/2013/101#revision1
Paper TR13-101
| A Uniform Min-Max Theorem with Applications in Cryptography |
Colin Jia Zheng,
Salil Vadhan
https://eccc.weizmann.ac.il/report/2013/101We 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 Freund and Schapire (Games and Economic Behavior '99) with the advantage that the algorithm runs in $\mathrm{poly}(n)$ time even when a pure strategy for the first player is a distribution chosen from a set of distributions over $\{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's Hardcore Theorem (FOCS '95); regularity theorems that provide efficient simulation of distributions within any sufficiently nice convex set (extending a result of Trevisan, Tulsiani and Vadhan (CCC '09)); an improved version of the Weak Regularity Lemma of Frieze and Kannan; a Dense Model Theorem for uniform algorithms; and showing impossibility of constructing Succinct Non-Interactive Arguments (SNARGs) via black-box reductions under uniform hardness assumptions (using techniques from Gentry and Wichs (STOC '11) for the nonuniform setting).Tue, 16 Jul 2013 01:16:46 +0300https://eccc.weizmann.ac.il/report/2013/101