T1: Compress Interactive Communication (2)

August 13, 2024

• Simulations
• Compressing Protocols without Private Randomness
• Compressing One-round Messages
• Reference

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.