arXiv:2403.00989 · IEEE Transactions on Information Theory

On Non-Interactive Simulation of Distributed Sources With Finite Alphabets

Hojat Allah Salehi, Farhad Shirani

Published Aug 11, 2025• 0 citations

Abstract

This work presents a Fourier analysis framework for the non-interactive source simulation (NISS) problem. Two distributed agents observe a pair of sequences$X^{d}$and$Y^{d}$drawn according to a joint distribution$P_{X^{d}Y^{d}}$. The agents aim to generate outputs$U=f_{d}(X^{d})$and$V=g_{d}(Y^{d})$with a joint distribution sufficiently close in total variation to a target distribution$Q_{UV}$. Existing works have shown that the NISS problem with finite-alphabet outputs is decidable. For the binary-output NISS, an upper-bound to the input complexity was derived which is$O\left ({{\exp \mathrm {poly}\left ({{\frac {1}{\epsilon }}}\right)}}\right)$. In this work, the input complexity and algorithm design are addressed in several classes of NISS scenarios. For binary-output NISS scenarios with doubly-symmetric binary inputs, it is shown that the input complexity is$\Theta \left ({{\log {\frac {1}{\epsilon }}}}\right)$, thus providing a super-exponential improvement in input complexity. An explicit characterization of the simulating pair of functions is provided. For general finite-input scenarios, a constructive algorithm is introduced that explicitly finds the simulating functions$(f_{d}(X^{d}),g_{d}(Y^{d}))$. The approach relies on a novel Fourier analysis framework. Various numerical simulations of NISS scenarios with IID inputs are provided. Furthermore, to illustrate the general applicability of the Fourier framework, several examples with non-IID inputs, including entanglement-assisted NISS and NISS with Markovian inputs are provided.

DOI: 10.1109/tit.2025.3597546

Related papers

On Non-Interactive Source Simulation via Fourier Transform

Farhad Shirani, Mohsen Heidari

arXiv:2212.09239IEEE Information Theory Workshop (ITW)Apr 23, 20233 citations

Quantum Advantage in Non-Interactive Source Simulation

Hojat Allah Salehi, Farhad Shirani, S. Sandeep Pradhan

arXiv:2402.00242IEEE International Symposium on Information Theory (ISIT)Jun 22, 20254 citations

Decidability of Non-interactive Simulation of Joint Distributions

Badih Ghazi, Pritish Kamath, Madhu Sudan

arXiv:1607.04322Annual Symposium on Foundations of Computer ScienceOct 1, 201627 citations

Distributed Source Simulation With No Communication

Tomer Berg, Ofer Shayevitz, Young-Han Kim +1 more

arXiv:1906.06970IEEE Transactions on Information TheoryOct 28, 20202 citations

On Non-Interactive Simulation of Joint Distributions

Sudeep Kamath, Venkat Anantharam

arXiv:1505.00769IEEE Transactions on Information TheoryApr 13, 201639 citations

Some Results on Distributed Source Simulation with no Communication

Tomer Berg, Ofer Shayevitz, Young-Han Kim +1 more

IEEE Information Theory Workshop (ITW)Aug 1, 20190 citations

arXiv:2403.00989 · IEEE Transactions on Information Theory

On Non-Interactive Simulation of Distributed Sources With Finite Alphabets

Hojat Allah Salehi, Farhad Shirani

Published Aug 11, 2025• 0 citations

arXiv HTML PDF

Abstract

This work presents a Fourier analysis framework for the non-interactive source simulation (NISS) problem. Two distributed agents observe a pair of sequences

X^{d}

and

Y^{d}

drawn according to a joint distribution

P_{X^{d}Y^{d}}

. The agents aim to generate outputs

U=f_{d}(X^{d})

and

V=g_{d}(Y^{d})

with a joint distribution sufficiently close in total variation to a target distribution

Q_{UV}

. Existing works have shown that the NISS problem with finite-alphabet outputs is decidable. For the binary-output NISS, an upper-bound to the input complexity was derived which is

O\left ({{\exp \mathrm {poly}\left ({{\frac {1}{\epsilon }}}\right)}}\right)

. In this work, the input complexity and algorithm design are addressed in several classes of NISS scenarios. For binary-output NISS scenarios with doubly-symmetric binary inputs, it is shown that the input complexity is

\Theta \left ({{\log {\frac {1}{\epsilon }}}}\right)

, thus providing a super-exponential improvement in input complexity. An explicit characterization of the simulating pair of functions is provided. For general finite-input scenarios, a constructive algorithm is introduced that explicitly finds the simulating functions

(f_{d}(X^{d}),g_{d}(Y^{d}))

. The approach relies on a novel Fourier analysis framework. Various numerical simulations of NISS scenarios with IID inputs are provided. Furthermore, to illustrate the general applicability of the Fourier framework, several examples with non-IID inputs, including entanglement-assisted NISS and NISS with Markovian inputs are provided.

DOI: 10.1109/tit.2025.3597546

Related papers

On Non-Interactive Source Simulation via Fourier Transform

Farhad Shirani, Mohsen Heidari

The non-interactive source simulation (NISS) scenario is considered. In this scenario, a pair of distributed agents, Alice and Bob, observe a distributed binary memoryless source (Xd,Yd) generated based on joint distribution PX,Y. The agents wish to produce a pair of discrete random variables (Ud,Vd) with joint distribution ${P_{{U_d},{V_d}}},$ such that ${P_{{U_d},{V_d}}}$ converges in total variation distance to a target distribution QU,Vas the input blocklength d is taken to be asymptotically large. Inner and outer bounds are obtained on the set of distributions QU,Vwhich can be produced given an input distribution PX,Y. To this end, a bijective mapping from the set of distributions QU,Vto a union of star-convex sets is provided. By leveraging proof techniques from discrete Fourier analysis along with a novel randomized rounding technique, inner and outer bounds are derived for each of these star-convex sets, and by inverting the aforementioned bijective mapping, necessary and sufficient conditions on QU,Vand PX,Yare provided under which QU,Vcan be produced from PX,Y. The bounds are applicable in NISS scenarios where the output alphabets ${\mathcal{U}}{\text{and}}{\mathcal{V}}$ have arbitrary finite size. In case of binary output alphabets, the outer-bound recovers the previously best-known outer-bound.The non-interactive source simulation (NISS) scenario is considered. In this scenario, a pair of distributed agents, Alice and Bob, observe a distributed binary memoryless source (Xd,Yd) generated based on joint distribution PX,Y. The agents wish to produce a pair of discrete random variables (Ud,Vd) with joint distribution ${P_{{U_d},{V_d}}},$ such that ${P_{{U_d},{V_d}}}$ converges in total variation distance to a target distribution QU,Vas the input blocklength d is taken to be asymptotically large. Inner and outer bounds are obtained on the set of distributions QU,Vwhich can be produced given an input distribution PX,Y. To this end, a bijective mapping from the set of distributions QU,Vto a union of star-convex sets is provided. By leveraging proof techniques from discrete Fourier analysis along with a novel randomized rounding technique, inner and outer bounds are derived for each of these star-convex sets, and by inverting the aforementioned bijective mapping, necessary and sufficient conditions on QU,Vand PX,Yare provided under which QU,Vcan be produced from PX,Y. The bounds are applicable in NISS scenarios where the output alphabets ${\mathcal{U}}{\text{and}}{\mathcal{V}}$ have arbitrary finite size. In case of binary output alphabets, the outer-bound recovers the previously best-known outer-bound.

arXiv:2212.09239IEEE Information Theory Workshop (ITW)Apr 23, 20233 citations

Quantum Advantage in Non-Interactive Source Simulation

Hojat Allah Salehi, Farhad Shirani, S. Sandeep Pradhan

This work considers the non-interactive source simulation problem (NISS). In the standard NISS scenario, a pair of distributed agents observe a distributed binary memoryless source ( $X^{d}, Y^{d}$ ) generated based on the joint distribution $P_{X, Y}$ . The agents wish to produce a pair of discrete random variables $\left(U_{d}, V_{d}\right)$ with joint distribution $P_{U_{d}, V_{d}}$ , such that $P_{U_{d}, V_{d}}$ converges in total variation distance to a target distribution $Q_{U, V}$ . Two variations of the standard NISS scenario are considered. In the first variation, in addition to $\left(X^{d}, Y^{d}\right)$ , the agents have access to a shared Bell state. They each measure their respective state, using a measurement of their choice, and use its classical output along with $\left(X^{d}, Y^{d}\right)$ to simulate the target distribution. This scenario is called the entanglement-assisted NISS (EA-NISS). In the second variation, the agents have access to a classical common random bit $Z$ , in addition to ( $X^{d}, Y^{d}$ ). This scenario is called the common randomness NISS (CR-NISS). It is shown that for binary output NISS scenarios, the set of simulatable distributions for EA-NISS and CR-NISS are equal with each other. Hence, there is no quantum advantage in these EA-NISS scenarios. For non-binary output NISS, it is shown that in a specific class of scenarios, the set of CR-NISS simulatable distributions forms a measure zero subset of EA-NISS simulatable distributions. A numerical example is provided, where the set of EA-NISS simulatable distributions strictly contains the set of CR-NISS simulatable distributions. This shows that there is a quantum advantage in non-binary output EA-NISS.This work considers the non-interactive source simulation problem (NISS). In the standard NISS scenario, a pair of distributed agents observe a distributed binary memoryless source ($X^{d}, Y^{d}$) generated based on the joint distribution$P_{X, Y}$. The agents wish to produce a pair of discrete random variables$\left(U_{d}, V_{d}\right)$with joint distribution$P_{U_{d}, V_{d}}$, such that$P_{U_{d}, V_{d}}$converges in total variation distance to a target distribution$Q_{U, V}$. Two variations of the standard NISS scenario are considered. In the first variation, in addition to$\left(X^{d}, Y^{d}\right)$, the agents have access to a shared Bell state. They each measure their respective state, using a measurement of their choice, and use its classical output along with$\left(X^{d}, Y^{d}\right)$to simulate the target distribution. This scenario is called the entanglement-assisted NISS (EA-NISS). In the second variation, the agents have access to a classical common random bit$Z$, in addition to ($X^{d}, Y^{d}$). This scenario is called the common randomness NISS (CR-NISS). It is shown that for binary output NISS scenarios, the set of simulatable distributions for EA-NISS and CR-NISS are equal with each other. Hence, there is no quantum advantage in these EA-NISS scenarios. For non-binary output NISS, it is shown that in a specific class of scenarios, the set of CR-NISS simulatable distributions forms a measure zero subset of EA-NISS simulatable distributions. A numerical example is provided, where the set of EA-NISS simulatable distributions strictly contains the set of CR-NISS simulatable distributions. This shows that there is a quantum advantage in non-binary output EA-NISS.

arXiv:2402.00242IEEE International Symposium on Information Theory (ISIT)Jun 22, 20254 citations

Decidability of Non-interactive Simulation of Joint Distributions

Badih Ghazi, Pritish Kamath, Madhu Sudan

We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions P(x, y) and Q(u, v): The goal is to determine if two players, Alice and Bob, that observe sequences Xn and Yn respectively where {(Xi, Yi)}ni = 1 are drawn i.i.d. from P(x, y) can generate pairs U and V respectively (without communicating with each other) with a joint distribution that is arbitrarily close in total variation to Q(u, v). Even when P and Q are extremely simple: e.g., P is uniform on the triples (0, 0), (0,1), (1,0) and Q is a "doubly symmetric binary source", i.e., U and V are uniform ± 1 variables with correlation say 0.49, it is open if P can simulate Q. In this work, we show that whenever P is a distribution on a finite domain and Q is a 2 × 2 distribution, then the non-interactive simulation problem is decidable: specifically, given δ > 0 the algorithm runs in time bounded by some function of P and δ and either gives a non-interactive simulation protocol that is δ-close to Q or asserts that no protocol gets O(δ)-close to Q. The main challenge to such a result is determining explicit (computable) convergence bounds on the number n of samples that need to be drawn from P(x, y) to get δ-close to Q. We invoke contemporary results from the analysis of Boolean functions such as the invariance principle and a regularity lemma to obtain such explicit bounds.We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions P(x, y) and Q(u, v): The goal is to determine if two players, Alice and Bob, that observe sequences Xn and Yn respectively where {(Xi, Yi)}ni = 1 are drawn i.i.d. from P(x, y) can generate pairs U and V respectively (without communicating with each other) with a joint distribution that is arbitrarily close in total variation to Q(u, v). Even when P and Q are extremely simple: e.g., P is uniform on the triples (0, 0), (0,1), (1,0) and Q is a "doubly symmetric binary source", i.e., U and V are uniform ± 1 variables with correlation say 0.49, it is open if P can simulate Q. In this work, we show that whenever P is a distribution on a finite domain and Q is a 2 × 2 distribution, then the non-interactive simulation problem is decidable: specifically, given δ > 0 the algorithm runs in time bounded by some function of P and δ and either gives a non-interactive simulation protocol that is δ-close to Q or asserts that no protocol gets O(δ)-close to Q. The main challenge to such a result is determining explicit (computable) convergence bounds on the number n of samples that need to be drawn from P(x, y) to get δ-close to Q. We invoke contemporary results from the analysis of Boolean functions such as the invariance principle and a regularity lemma to obtain such explicit bounds.

arXiv:1607.04322Annual Symposium on Foundations of Computer ScienceOct 1, 201627 citations

Distributed Source Simulation With No Communication

Tomer Berg, Ofer Shayevitz, Young-Han Kim +1 more

We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences $U^{n}$ and $V^{n}$ respectively, drawn from a joint distribution $p_{UV}^ {\otimes n}$ , and wish to locally generate sequences $X^{n}$ and $Y^{n}$ respectively with a joint distribution that is close (in KL divergence) to $p_{XY}^ {\otimes n}$ . We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between $U$ and $V$ is nonzero, and we conjecture that only scalar Markov chains $X-U-V-Y$ can be simulated otherwise. Motivated by this conjecture, we further examine the case where both $p_{UV}$ and $p_{XY}$ are doubly symmetric binary sources with parameters $p,q\leq 1/2$ respectively. While it is trivial that in this case $p\leq q$ is both necessary and sufficient, we use Fourier analytic tools to show that when $p$ is close to $q$ then any successful simulation is close to being scalar in the total variation sense.We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences$U^{n}$and$V^{n}$respectively, drawn from a joint distribution$p_{UV}^ {\otimes n}$, and wish to locally generate sequences$X^{n}$and$Y^{n}$respectively with a joint distribution that is close (in KL divergence) to$p_{XY}^ {\otimes n}$. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between$U$and$V$is nonzero, and we conjecture that only scalar Markov chains$X-U-V-Y$can be simulated otherwise. Motivated by this conjecture, we further examine the case where both$p_{UV}$and$p_{XY}$are doubly symmetric binary sources with parameters$p,q\leq 1/2$respectively. While it is trivial that in this case$p\leq q$is both necessary and sufficient, we use Fourier analytic tools to show that when$p$is close to$q$then any successful simulation is close to being scalar in the total variation sense.

arXiv:1906.06970IEEE Transactions on Information TheoryOct 28, 20202 citations

On Non-Interactive Simulation of Joint Distributions

Sudeep Kamath, Venkat Anantharam

We consider the following non-interactive simulation problem: Alice and Bob observe sequences Xnand Yn, respectively, where ((Xi, Yi)}i=1nare drawn independent identically distributed 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.We consider the following non-interactive simulation problem: Alice and Bob observe sequences Xnand Yn, respectively, where ((Xi, Yi)}i=1nare drawn independent identically distributed 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.

arXiv:1505.00769IEEE Transactions on Information TheoryApr 13, 201639 citations

Some Results on Distributed Source Simulation with no Communication

Tomer Berg, Ofer Shayevitz, Young-Han Kim +1 more

We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Unand Vnrespectively, drawn from a joint distribution $p_{UV}^{\otimes n}$ , and wish to locally generate sequences Xnand Ynrespectively with a joint distribution that is close (in KL divergence) to $p_{XY}^{\otimes n}$ . We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains $X-U-V-Y$ can be simulated otherwise. Motivated by this conjecture, we further examine the case where both pUVand pXYare doubly symmetric binary sources with parameters $p, q\leq 1/2$ respectively. While it is trivial that in this case $p\leq q$ is both necessary and sufficient, we show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Unand Vnrespectively, drawn from a joint distribution $p_{UV}^{\otimes n}$, and wish to locally generate sequences Xnand Ynrespectively with a joint distribution that is close (in KL divergence) to $p_{XY}^{\otimes n}$. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains $X-U-V-Y$ can be simulated otherwise. Motivated by this conjecture, we further examine the case where both pUVand pXYare doubly symmetric binary sources with parameters $p, q\leq 1/2$ respectively. While it is trivial that in this case $p\leq q$ is both necessary and sufficient, we show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.

IEEE Information Theory Workshop (ITW)Aug 1, 20190 citations

This work presents a Fourier analysis framework for the non-interactive source simulation (NISS) problem. Two distributed agents observe a pair of sequences

X^{d}

and

Y^{d}

drawn according to a joint distribution

P_{X^{d}Y^{d}}

. The agents aim to generate outputs

U=f_{d}(X^{d})

and

V=g_{d}(Y^{d})

with a joint distribution sufficiently close in total variation to a target distribution

Q_{UV}

. Existing works have shown that the NISS problem with finite-alphabet outputs is decidable. For the binary-output NISS, an upper-bound to the input complexity was derived which is

O\left ({{\exp \mathrm {poly}\left ({{\frac {1}{\epsilon }}}\right)}}\right)

\Theta \left ({{\log {\frac {1}{\epsilon }}}}\right)

(f_{d}(X^{d}),g_{d}(Y^{d}))

{P_{{U_d},{V_d}}},

such that

{P_{{U_d},{V_d}}}

converges in total variation distance to a target distribution QU,Vas the input blocklength d is taken to be asymptotically large. Inner and outer bounds are obtained on the set of distributions QU,Vwhich can be produced given an input distribution PX,Y. To this end, a bijective mapping from the set of distributions QU,Vto a union of star-convex sets is provided. By leveraging proof techniques from discrete Fourier analysis along with a novel randomized rounding technique, inner and outer bounds are derived for each of these star-convex sets, and by inverting the aforementioned bijective mapping, necessary and sufficient conditions on QU,Vand PX,Yare provided under which QU,Vcan be produced from PX,Y. The bounds are applicable in NISS scenarios where the output alphabets

{\mathcal{U}}{\text{and}}{\mathcal{V}}

have arbitrary finite size. In case of binary output alphabets, the outer-bound recovers the previously best-known outer-bound.

This work considers the non-interactive source simulation problem (NISS). In the standard NISS scenario, a pair of distributed agents observe a distributed binary memoryless source (

X^{d}, Y^{d}

) generated based on the joint distribution

P_{X, Y}

. The agents wish to produce a pair of discrete random variables

\left(U_{d}, V_{d}\right)

with joint distribution

P_{U_{d}, V_{d}}

, such that

P_{U_{d}, V_{d}}

converges in total variation distance to a target distribution

Q_{U, V}

. Two variations of the standard NISS scenario are considered. In the first variation, in addition to

\left(X^{d}, Y^{d}\right)

, the agents have access to a shared Bell state. They each measure their respective state, using a measurement of their choice, and use its classical output along with

\left(X^{d}, Y^{d}\right)

to simulate the target distribution. This scenario is called the entanglement-assisted NISS (EA-NISS). In the second variation, the agents have access to a classical common random bit

Z

, in addition to (

X^{d}, Y^{d}

). This scenario is called the common randomness NISS (CR-NISS). It is shown that for binary output NISS scenarios, the set of simulatable distributions for EA-NISS and CR-NISS are equal with each other. Hence, there is no quantum advantage in these EA-NISS scenarios. For non-binary output NISS, it is shown that in a specific class of scenarios, the set of CR-NISS simulatable distributions forms a measure zero subset of EA-NISS simulatable distributions. A numerical example is provided, where the set of EA-NISS simulatable distributions strictly contains the set of CR-NISS simulatable distributions. This shows that there is a quantum advantage in non-binary output EA-NISS.

We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences

U^{n}

and

V^{n}

respectively, drawn from a joint distribution

p_{UV}^ {\otimes n}

, and wish to locally generate sequences

X^{n}

and

Y^{n}

respectively with a joint distribution that is close (in KL divergence) to

p_{XY}^ {\otimes n}

. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between

U

and

V

is nonzero, and we conjecture that only scalar Markov chains

X-U-V-Y

can be simulated otherwise. Motivated by this conjecture, we further examine the case where both

p_{UV}

and

p_{XY}

are doubly symmetric binary sources with parameters

p,q\leq 1/2

respectively. While it is trivial that in this case

p\leq q

is both necessary and sufficient, we use Fourier analytic tools to show that when

p

is close to

q

then any successful simulation is close to being scalar in the total variation sense.

We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Unand Vnrespectively, drawn from a joint distribution

p_{UV}^{\otimes n}

, and wish to locally generate sequences Xnand Ynrespectively with a joint distribution that is close (in KL divergence) to

p_{XY}^{\otimes n}

X-U-V-Y

can be simulated otherwise. Motivated by this conjecture, we further examine the case where both pUVand pXYare doubly symmetric binary sources with parameters

p, q\leq 1/2

respectively. While it is trivial that in this case

p\leq q

is both necessary and sufficient, we show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.