Lower Bounds for Interactive Function Computation via Wyner Common Information

Shijin Rajakrishnan, Sundara Rajan S, Vinod Prabhakaran

The question of how much communication is required between collaborating parties to compute a function of their data is of fundamental importance in the fields of theoretical compu…