LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
The Communication Complexity of Distributed Estimation
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

The Communication Complexity of Distributed Estimation

109 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

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.

At a glance

Lecture facts

Runtime compared with the other 350 Mathematics lectures
Runtime1 h 49 m
Compared with MathematicsLonger than 95%
Source channelInstitute for Advanced Study (YouTube)
Link status✓ Working · checked today
QA · not live