<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=iso-8859-1"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:"Calibri Light";
panose-1:2 15 3 2 2 2 4 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
h1
{mso-style-priority:9;
mso-style-link:"Heading 1 Char";
margin-top:24.0pt;
margin-right:0in;
margin-bottom:0in;
margin-left:0in;
margin-bottom:.0001pt;
page-break-after:avoid;
font-size:14.0pt;
font-family:"Calibri Light",sans-serif;
color:#2E74B5;
font-weight:bold;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.Heading1Char
{mso-style-name:"Heading 1 Char";
mso-style-priority:9;
mso-style-link:"Heading 1";
font-family:"Calibri Light",sans-serif;
color:#2E74B5;
font-weight:bold;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.EmailStyle20
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle21
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle22
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle23
{mso-style-type:personal;
font-family:"Times New Roman",serif;
color:windowtext;}
span.EmailStyle24
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle25
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle26
{mso-style-type:personal;
font-family:"Times New Roman",serif;
color:windowtext;}
span.EmailStyle27
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle28
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle29
{mso-style-type:personal;
font-family:"Times New Roman",serif;
color:windowtext;}
span.EmailStyle30
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle31
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle32
{mso-style-type:personal;
font-family:"Times New Roman",serif;
color:windowtext;}
span.EmailStyle33
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle34
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle35
{mso-style-type:personal;
font-family:"Times New Roman",serif;
color:windowtext;}
span.EmailStyle36
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle37
{mso-style-type:personal;
font-family:"Times New Roman",serif;
color:windowtext;}
span.EmailStyle38
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle39
{mso-style-type:personal;
font-family:"Times New Roman",serif;
color:windowtext;}
span.EmailStyle40
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle41
{mso-style-type:personal;
font-family:"Times New Roman",serif;
color:windowtext;}
span.EmailStyle42
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle43
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle44
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:#1F497D;}
span.EmailStyle45
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link="#0563C1" vlink="#954F72"><div class=WordSection1><p class=MsoNormal><span style='font-family:"Times New Roman",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-bottom:12.0pt'><b><span style='font-size:14.0pt;font-family:"Times New Roman",serif'>===== Today’s ORFE Department Colloquium Announcement=====</span></b><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:14.0pt;font-family:"Times New Roman",serif'>DATE: Tuesday, September 25th, 2018 </span><span style='font-family:"Times New Roman",serif'><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:14.0pt;font-family:"Times New Roman",serif'> </span><span style='font-family:"Times New Roman",serif'><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:14.0pt;font-family:"Times New Roman",serif'>TIME: 4:30pm </span><span style='font-family:"Times New Roman",serif'><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:14.0pt;font-family:"Times New Roman",serif'> </span><span style='font-family:"Times New Roman",serif'><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:14.0pt;font-family:"Times New Roman",serif'>LOCATION: <span style='color:#1F497D'> </span>Sherrerd Hall 101</span><span style='font-family:"Times New Roman",serif'><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:14.0pt;font-family:"Times New Roman",serif'> </span><span style='font-family:"Times New Roman",serif'><o:p></o:p></span></p><p class=MsoNormal><b><span style='font-size:14.0pt;font-family:"Times New Roman",serif'>SPEAKER:</span></b><span style='font-size:14.0pt;font-family:"Times New Roman",serif'> Yuval Peres, Microsoft Research</span><span style='font-family:"Times New Roman",serif'><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:14.0pt;font-family:"Times New Roman",serif'> </span><span style='font-family:"Times New Roman",serif'><o:p></o:p></span></p><h1 style='mso-margin-top-alt:0in;margin-right:0in;margin-bottom:12.0pt;margin-left:0in;background:white'><span style='font-size:16.0pt;font-family:"Times New Roman",serif;color:windowtext'>Title:</span><span style='font-family:"Times New Roman",serif;color:windowtext'> </span><span style='font-family:"Times New Roman",serif;color:#1F497D'> </span><span style='font-size:16.5pt;font-family:"Arial",sans-serif;color:black'>Communication cost of consensus for nodes with limited memory<o:p></o:p></span></h1><h1 style='mso-margin-top-alt:6.0pt;margin-right:0in;margin-bottom:6.0pt;margin-left:0in;background:white'><span style='font-family:"Times New Roman",serif;color:windowtext'> <o:p></o:p></span></h1><p style='mso-margin-top-alt:6.0pt;margin-right:0in;margin-bottom:6.0pt;margin-left:0in;background:white'><b><span style='font-size:16.0pt'>Abstract:</span></b><b><span style='font-size:14.0pt'> </span></b><span style='font-family:"Arial",sans-serif;color:#3B3B3B;background:white'>Motivated by applications in blockchain and sensor networks, we consider a model of n nodes trying to reach consensus on their majority bit (which a fraction p>1/2 of them possess; the rest start with the minority bit). Each node v is a finite automaton with m bits of memory (i.e., 2^m states), and a Poisson clock. When it rings, the node v can choose to communicate, and is then matched to a uniformly chosen node u, whence both v,u can update their states based on the other nodes’ state. Previous work has focused on minimizing the time to consensus and the probability of error; our goal is minimizing communication. We show that when m>3 logloglog(n), consensus can be reached at linear communication cost, but this is impossible if m<logloglog(n). The best algorithms we know intrinsically select a set of “expert” nodes that learn the majority bit, and then disseminate this knowledge. A key step is to distinguish when nodes can become “aware” of reaching the majority bit and stop communicating; this is impossible if their memory is too low. (Joint work with Giulia Fanti, Nina Holden and Gireeja Ranade).</span><span style='font-size:11.0pt'><o:p></o:p></span></p><div class=MsoNormal align=center style='text-align:center'><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><hr size=1 width="100%" noshade style='color:#3B3B3B' align=center></span></div><p class=MsoNormal style='mso-margin-top-alt:6.0pt;margin-right:0in;margin-bottom:6.0pt;margin-left:0in;background:white'><b><span style='font-size:14.0pt;font-family:"Times New Roman",serif'>Biography:</span></b><span style='font-family:"Times New Roman",serif'> </span><span style='font-family:"Arial",sans-serif;color:#3B3B3B;background:white'>Yuval Peres is a Principal Researcher at Microsoft Research in Redmond. He obtained his Ph.D. at the Hebrew University, Jerusalem in 1990, and later taught there and at the University of California, Berkeley. He has published more than 300 research papers and has co-authored books on Brownian motion, Markov chains, Probability on Networks, Fractals, and Game Theory. Yuval was awarded the Rollo Davidson Prize in 1995, the Loève Prize in 2001, and the David P. Robbins Prize in 2011. He was an invited speaker at the 2002 International Congress of Math. and in the 2008 European Congress, and was a plenary lecturer at the Math. Congress of the Americas in 2017. He has advised 22 Ph.D. students. He is a fellow of the American Math. Society and the Institute of Mathematical Statistics. In 2016 he was elected to the U.S. National Academy of Sciences.</span><span style='font-family:"Times New Roman",serif;color:#1F497D'><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:14.0pt'><o:p> </o:p></span></p><p class=MsoNormal><o:p> </o:p></p></div></body></html>