On Non-Interactive Simulation of Joint Distributions

DOI10.1109/TIT.2016.2553672MaRDI QIDQ2976791zbMATH OpenOpenAlexFDO

Authors Sudeep Kamath, Venkat Anantharam

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.00769

Abstract: We consider the following non-interactive simulation problem: Alice and Bob observe sequences

X^{n}

and

Y^{n}

respectively where

{(X_{i}, Y_{i})}_{i = 1}^{n}

are drawn i.i.d. from

P (x, y),

and they output

U

and

V

respectively which is required to have a joint law that is close in total variation to a specified

Q (u, v) .

It is known that the maximal correlation of

U

and

V

must necessarily be no bigger than that of

X

and

Y

if this is to be possible. Our main contribution is to bring hypercontractivity to bear as a tool on this problem. In particular, we show that if

P (x, y)

is the doubly symmetric binary source, then hypercontractivity provides stronger impossibility results than maximal correlation. Finally, we extend these tools to provide impossibility results for the

k

-agent version of this problem.

Cited in

(13)

This page was built for publication: On Non-Interactive Simulation of Joint Distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2976791)