The Toffoli gate is a 3-input, 3-output classical logic gate. It sends $(x, y, a)$ to $(x, y, a \oplus (x \cdot y))$. It is significant in that it is universal for reversible (classical) computation.
The Popescu-Rohrlich box is the simplest example of a non-signaling correlation. It takes a pair of inputs $(x, y)$ and outputs $(a, b)$ satisfying $x \cdot y = a \oplus b$ such that $a$ and $b$ are both uniform random variables. It is universal for a certain class of (but not all) non-signaling correlations.
To my eye, these two objects look extremely similar, especially if we augment the PR box by having it output $(x, y, a, b) = (x, y, a, a \oplus (x \cdot y))$. This 2-input, 4-output PR box "is" the 3-input, 3-output Toffoli gate but with the third input replaced by a random output. But I've been unable to locate any references that relate them.
What is the relationship between the Toffoli gate and the Popescu-Rohrlich box? Is there something like a correspondence between reversible classical circuits and (a certain class of?) non-signaling correlations that maps one to the other?
Specifying a non-signaling correlation requires not just a function but also an assignment of each input and output to a party that controls it. A PR box is no longer non-signaling if we allow Alice to enter both inputs and Bob to read both outputs. Or in our "augmented" PR-box, if Alice inputs $x$, she must also be the one who reads the copy of $x$. So it seems nontrivial to determine, for a general circuit (with some inputs possibly replaced by random outputs), all the ways inputs and outputs can be assigned to parties such that communication is not possible.
We can apply the above procedure any logic gate, including irreversible ones. For instance, we can take AND and replace one of the inputs by a random output, and get a function one input $x$ and a pair $(a, x \cdot a)$ where $a$ is a uniform random variable. However, $x \cdot a$ is $0$ conditioned on $x = 0$, so the only way this can be non-signaling is if Alice, who inputs $x$, receives $x \cdot a$. But this procedure can already be reproduced classically with a shared source of randomness. So I would expect that including irreversible gates does not expand the class of non-signaling correlations one can construct.