Reference - this survey: https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf

I am reading the section on constructing lossless conductors using a bipartite variant of zigzag product (section 10, proof of theorem 10.2.2). I am having trouble following a line in the proof- in page 521 eq (20), the authors write:

Therefore, $k+a = H_{\infty}(X_1, X_2, R_2) = H_{\infty}(X_1, Y_2, Z_2) = H_{\infty} (Y_1, Z_1, Z_2)$. To conclude the argument, consider any $y_1 \in \text{supp}(Y_1)$ and note that by the bound on the total entropy and the lower bound proved above for $H_{\infty} (Y_1)$ ($H_{\infty}(Y_1) \geq k-14a$), we must have $H_{\infty}(Z_1, Z_2|Y_1=y_1) \leq 15a$

(For reference, the support of $(Z_1, Z_2)$ is $\{0,1\}^{35a}$.) I don't see why this follows. For example why can't the distribution of $Z_1,Z_2$ conditioned on $Y_1=y_1$ be uniform for certain values of $y_1$ (and for those values of $y_1$, the third step does not transfer all the entropy)?

One fix I can think of it is this: we can assume the source distribution is the uniform distribution on a set of size $2^k$ (since any distribution with min entropy $k$ can be written as a convex combination of distributions of this form). In this case $p(y_1,z_1,z_2) = 1/2^{k+a}$ for all $(y_1,z_1,z_2)$ in the support - and the upper bound on $H_{\infty}(Z_1,Z_2|Y_1=y_1)$ holds. But I don't see how this follows just from the assumption that $H_{\infty}(Y_1,Z_1,Z_2)=k+a$. Am I missing something?

  • $\begingroup$ Would it make sense to contact the author(s) rather than hope that somebody who's very familiar with the paper chimes on? $\endgroup$
    – Kai
    Aug 30, 2023 at 16:12


Your Answer

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