On Uniform Reductions between Direct Product and XOR Lemmas

by Ragesh Jaiswal

Oded's comments

My interest in this work is focused at the new reductions it presents between the "XOR Lemma" and the "Selective XOR Lemma" (see Exer. 7.17 and 7.18 in my complexity book). Specifically, for a Boolean function $f:\{0,1\}^n\to\{0,1\}$, in the XOR Lemma one is given $k$ random strings $x_1,...,x_k$ and is asked to guess $\xor_{i\in[k]} f(x_i)$, whereas in the Selective XOR Lemma one is given $k$ random strings $x_1,...,x_k$ along with a random set $S\subseteq[k]$. and is asked to guess $\xor_{i\in S} f(x_i)$.

In Exer 7.17, the second task is reduced to the first task by using $k$ auxiliary strings $z_i$ along with the corresponding values $b_i=f(z_i)$. This requires either hardwiring these values (i.e., non-uniformity) or being able to sample pairs of the form $(z,f(z))$. In any case, $\xor_{i\in S} f(x_i)$ is guessed by guessing $b = \xor_{i\in[k]} f(y_i))$ and outputting $b \xor (\xor_{i\in[k]-S} b_i)$, where $y_i=x_i$ if $i\in S$ and $y_i=z_i$ o.w.

In the proof of Thm 1 presented in this paper, $\xor_{i\in S} f(x_i)$ is guessed at random if $|S|$ is odd and guessed to equal $\xor_{i\in[k]} f(x'_i)) \xor (\xor_{i\in[k]} f(x''_i))$, where $x'$ and $x''$ split the $|S|$ relevant blocks of $x$ (at random) and are augmented by the same $k-(|S|/2)$ auxiliary random strings (with no need to guess their $f$-value). Indeed, that's a nicer reduction! But it means that the advantage is squared (i.e., decreases from $\e$ to $\e^2$ or so).

The core of the analysis is presented in Lemma 3.

The original abstract

There is a close connection between Direct Product and XOR lemmas in the sense that in many settings, we can prove one given the other. The known reductions that are used for the above purpose are either in the non-uniform setting or give non-matching parameters. By non-matching parameter we mean that k-wise Direct Product lemma implies k'-wise XOR lemma (and vice versa) for k' neq k. In this work, we discuss reductions between k-wise Direct Product and k-wise XOR lemmas. That is, we show that if the k-wise direct product lemma holds, then so does the k-wise XOR lemma and vice versa. We show that even though there is a perfectly uniform reduction in one direction, the reduction in the other direction requires some amount of non-uniformity. We give reductions in both directions matching information-theoretic bounds up to polynomial factors. Our techniques also give a small quantitative improvement over the known results about proving k-wise XOR lemma using 2k-wise Direct Product lemma.

See arxiv record.


Back to list of Oded's choices.