A Uniform Min-Max Theorem with Applications in Cryptography

by Salil Vadhan and Colin Jia Zheng

Oded's comments

I was intrigued by the title and abstract, but found the text quite confusing and unclear. So I asked Salil for some clarifications.

It turns out that a special case of the Uniform Min-Max Theorem was used in the authors' prior paper (see my choice Nr. 81), but its wider context and applications were not explored (and its presentation and proof were tersed). The current paper is supposed to do that (i.e., provide a general statement as well as explore the numerous applications), but it does not do so well enough (i.e., from an exposition point of view). Below, I wish to clarify one issue, which is the actual message underlying the current Thm 3.1.

In my opinion, Thm 3.1 is a lemma that should be stated after presenting the algorithmic scheme of Alg 3.1. The actual theorem should be stated in terms that do not refer to the execution of that algorithm, but rather refer to general guarantees regarding the oracles that it uses. (It seems that the authors wanted to avoid formulating general conditions and general guarantees, since they feared these may be too complex to fit all applications (let alone those not explored yet); thus, they preferred to just refer to objects produced during the execution of the algorithm when using some generic procedures; needless to say, I disagree with their choice.)

Specifically, the theorem should refer to three oracles, which work with descriptions of strategies for the two parties (using a $V$-strategy and a $W$-strategy, resp.). The forms of these descriptions may be arbitrary, but they are fixed for the theorem; these forms (i.e., descryption languages) depend on the application. (Indeed, the description of strategies for each of the two parties may be different (since $V$ is typically a distribution over $[N]$, whereas $W$ is a Boolean function over $[N]$).) The oracles are:

  1. Strategy Selection Oracle (SSO) mapping descriptions of V-strategies to descriptions of W-strategies. This oracle is typically a hypothesis of the application (i.e., it is provided by a user/adversary).
  2. Weight Update Oracle (WUO) that modifies a given (description of a) V-strategy according to a given (description of a) W-strategy. This modification must satisfy a specific condition (i.e., "exponential decay"), and it provided by the "designers" (i.e., the authors) who wish to obtain a universal strategy.
  3. Projection Oracle (PO) modifies a given (description of a) V-strategy according to a specific condition (i.e., "entropy projection"), and like WUO it should be provided by the designers.
A simplified form of the theorem may say that if SSO returns a strategy $W$ that is approximately optimal w.r.t the given $V$-strategy (up to an additive slackness of $\lambda$), then we can obtain a universal strategy that is almost optimal (up to an additive slackness of $2\lambda$) within complexity $n'/\e^2$ (i.e., this number of oracle calls), where $n' \leq \log_2 N$ is the entropy deficiency of the class of distributions (from which the $V$-strategy can be taken) and $\e$ is the slackness in PO (which also effects the condition in WUO). The actual running-time will depend on the running-time of the implementations of the various oracles, where above I assumed for simplicity that all oracle calls are with descriptions of fixed length (where is the earlier calls longer padding to this length is used).

Salil commented that this simplified form does not suffice for the applications, and it needs to be generalized to refer to more general forms of performace guarantee of the SSO. Specifically, it may be that we are only guaranteed that SSO gets payoff $p$ for any $V$-strategy of a certain class (where $p$ may be far from the optimum even for that class). In such a case, we obtain a universal strategy that yields payoff at least $p-\lambda$ (for the said class).

I wonder if one really need the current statement of Thm 3.1, which refers to arbitrary SSO's (lacking any "global" guarantee) and thus must refer to their "pointwise" performance (which leads to referring to the $V$'s and $W$'s that occur in the execution of the algorithm). Regardless of the answer, I think this should be a lemma that follows the presentation of the "algorithmic schema" (Alg 3.1).

The original abstract

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 Freund and Schapire (Games and Economic Behavior '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 $\{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).

See TR13-101.

Back to list of Oded's choices.