On Uniform Reductions between Direct Product and XOR Lemmas
Ragesh Jaiswal · arXiv (Cornell University) · 2014
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 eq 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.