I have been reading the proof in the following paper, and I am unable to understand some parts in the proof. This paper shows that a distribution $A$ over $[n]\times[m]$, $n\geq m$, can be $\epsilon$-tested for independence with just $\tilde{O}(n^{2/3}m^{1/3}\mathrm{poly}(\epsilon^{-1}))$ samples. As part of their technique in section 3.1, the authors employ bucketing, that is, each marginal distribution $\pi_i A$, $i=1,2$, is divided into buckets (say $\pi_1 A$), for some value $\epsilon'>0$:

$R_0:=\{i\in [n]:\pi_1 A(i)<1/n\log n\}$
$R_j:=\left\{i\in [n]:\frac{(1+\epsilon')^{j-1}}{n\log n}\leq \pi_1 A(i)\leq \frac{(1+\epsilon')^{j}}{n\log n}\right\}$

It is clear from the definition of bucketing that restricted to a bucket $R_j$ we have $d((\pi_1 A)|_{R_j},U_{R_j})\leq \epsilon'$, that is, the marginal distribution restricted to a bucket is $\epsilon'$-close to the uniform distribution.

My question: The above can also be written as $d(\pi_1 (A|_{R_j\times [m]}),U_{R_j})\leq \epsilon'$. If we bucket both the $\pi_1A$ marginal, $R_0,\ldots, R_k$, and the $\pi_2 A$ marginal, $S_0,\ldots, S_k$, can we also show that $d(\pi_1 (A|_{R_j\times S_\ell}),U_{R_j}),d(\pi_2 (A|_{R_j\times S_\ell}),U_{S_\ell})\leq \epsilon'$? This seems like an implicit assumption in the application of Lemma 19 in Section 3.1, page 6. This is used in step (6) of their algorithm, and the authors don't clarify why this is true.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.