Round-Preserving Asymptotic Compression of Prior-Free Interactive Protocols

Gurleen Padda, Dave Touchette

There is a close relationship between the communication complexity and information complexity of communication problems, as demonstrated by results such as Shannon's noiseless sour…