Reminder: This post contains 406 words
· 2 min read
· by Xianbin
Simulations
What is the simulation?
If we say a protocol \(\Pi'\) simulates \(\Pi\), if the leaves of the \(\Pi\) protocol tree can be transformed to the \(\Pi\) protocol tree and the distribution of leaves of \(\Pi\) is almost the distribution of leaves in \(\Pi'\).
Compressing Protocols without Private Randomness
Compressing One-round Messages
Reference
[1]. Rao, Anup, and Amir Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020.