Assume $X_1,...,X_t$ are independent distributions on $\mathbb{Z}_2^n$ s.t. each $X_i$ is $\epsilon$-close to min-entropy $k$; i.e. there exist distributions $Y_1,...,Y_t$ on $\mathbb{Z}_2^n$ s.t: $$ \forall i: \frac{1}{2}\sum_{x\in\mathbb{Z}_2^n}|X_i(x)-Y_i(x)|\leq\epsilon $$ and: $$ \forall i: H_\infty(Y_i)\geq k $$ where $H_\infty(Y_i)=\min_{x\in\mathbb{Z}_2^n}\{-\log_2(Y_i(x))\}$ is the min-entropy of $Y_i$.

Define $X=\sum_{i=1}^t X_i$ as the distribution corresponding to the convolution of $X_1,...,X_t$: $$ X(x)=\sum_{\substack{x_1,...,x_t\in\mathbb{Z}_2^n\\x_1\oplus...\oplus x_t=x}}\prod_{i=1}^t X_i(x_i) $$ How do I show that $X$ is $\epsilon^t$-close to min-entropy $k$?


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.