= Solution
Use $\oplus$ for <exclusive or> and regard all <bits> as elements of $\mathbb F_2$. For every public label $z\in\{0,1\}^m$, Alice computes the <indicator function>
$$
u_z(x)=\mathbf1_{\{x=z\}},
$$
while Bob computes $v_z(y)=f(z,y)$ from the known <truth table>. Exactly one of the $u_z(x)$ is one, so the <separated Boolean decomposition> is
$$
f(x,y)=\bigoplus_{z\in\{0,1\}^m}u_z(x)v_z(y).
$$
For each $z$, they invoke an independent <PR box> with respective input <bits> $u_z(x),v_z(y)$ and receive outputs $a_z,b_z$. These satisfy $a_z\oplus b_z=u_z(x)v_z(y)$. Alice forms $A=\bigoplus_z a_z$, and Bob forms $B=\bigoplus_z b_z$. Taking the <exclusive or> of all box constraints proves
$$
A\oplus B
=\bigoplus_z(a_z\oplus b_z)
=\bigoplus_z u_z(x)v_z(y)=f(x,y).
$$
Alice sends the single <bit> $A$. Bob combines it with his locally known $B$, obtaining
$$
\boxed{f(x,y)=A\oplus B,\qquad\text{one classical bit from Alice to Bob}.}
$$
This is <one-bit computation using Popescu–Rohrlich boxes>. It uses $2^m$ boxes; decomposing by Bob's input instead gives $2^n$, so the smaller truth-table factorization uses at most $2^{\min(m,n)}$. No efficiency bound on local calculation or box use is needed for the stated unlimited resource.
Each <PR box> has uniform local output distributions regardless of the other party's input. Independent invocations therefore give Bob a uniform output string before the message, carrying no information about $x$. The useful correlation becomes accessible through Alice's final <bit>; the construction respects the no-signalling property of the boxes.
Back to article page
