
The Communication Complexity of Distributed Estimation
Communication complexity gets a new twist in this Institute for Advanced Study seminar talk by Parikshit Gopalan of Apple, who extends Yao's two-party model so that Alice and Bob hold probability distributions over inputs rather than single values, and must jointly estimate the expectation of a function f within some error. Gopalan shows that problems already studied in sketching, databases, and learning theory are instances of this distributed estimation setup, then compares protocols: naive sampling needs communication scaling as one over epsilon squared, while his new debiasing protocol gets that down to linear in one over epsilon with better variance reduction. He introduces a spectral technique for proving lower bounds, establishing that the Equality function is the easiest full-rank Boolean function for this task, with set-disjointness as a notable exception. The talk draws on joint work with Raghu Meka, Prasad Raghavendra, Mihir Singhal, and Avi Wigderson, and runs as a full discrete mathematics seminar with blackboard-level technical detail.