<div dir="ltr"><span><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap"><br></span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap">Hi Everyone,</span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><br><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap"></span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap">This Friday Yuchen Zhang from Berkeley will talk about:</span></p><p style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap"><br></span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap">Title</span><span style="font-size:14.6667px;font-family:Arial;vertical-align:baseline;white-space:pre-wrap">: Communication complexity of statistical estimation and linear algebraic computation</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:14.6667px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">Abstra</span><span style="font-size:14.6667px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent">ct:</span><span style="font-size:14.6667px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap;background-color:transparent"> We study two distributed data processing tasks where communication is an efficiency bottleneck. The first task is distributed statistical estimation, where the data points are i.i.d. sampled from an underlying distribution, but stored across separate locations. The goal is to estimate a parameter of the distribution. We demonstrate that there is a fundamental trade-off between the statistical accuracy and the number of bits exchanged across the network, no matter how the algorithm is designed. </span><span style="font-size:14.6667px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap">The trade-off holds for a variety of problems, including location estimation in several families and parameter estimation in different types of regression models.</span></p><br><span style="font-size:14.6667px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap">The second task is to compute the generalized rank of an n-by-n matrix whose entries are stored across separate <span style="font-size:14.6667px;line-height:20.24px">locations</span>. The algorithm can output approximate solutions, but the goal is to communicate as little as possible. We show that any deterministic algorithm solving this problem must communicate Ω(n^2) bits, which is order-equivalent to transmitting the whole matrix. In contrast, we present a randomized algorithm that communicates only O(n) bits to compute good approximate solutions. The upper bound is matched by an Ω(n) lower bound on the randomized communication complexity.</span></span><br><div><span><span style="font-size:14.6667px;font-family:Arial;color:rgb(0,0,0);vertical-align:baseline;white-space:pre-wrap"></span></span><font face="Arial" color="#000000"><span style="font-size:14.6667px;white-space:pre-wrap"><br></span></font></div><div><font face="Arial" color="#000000"><span style="font-size:14.6667px;white-space:pre-wrap">See you Friday at 11am in the Stat&#39;s classroom.<br><br></span></font></div><div><font face="Arial" color="#000000"><span style="font-size:14.6667px;white-space:pre-wrap">Regards,<br></span></font></div><div><font face="Arial" color="#000000"><span style="font-size:14.6667px;white-space:pre-wrap">sekhar</span></font></div></div>