<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div class="gmail_default"><div><div><p class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_5987474974647831651gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_9103776001042077600gmail-p1" style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><b><font style="vertical-align:inherit"><font style="vertical-align:inherit">When: </font></font></b><font style="vertical-align:inherit"><font style="vertical-align:inherit"> Monday, May 20th at <b>11:00 am</b></font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><font style="vertical-align:inherit"><font style="vertical-align:inherit">Where: </font></font></b><font style="vertical-align:inherit"><font style="vertical-align:inherit">TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b></font></font>Ronitt Rubinfeld, MIT and Tel Aviv University</font></p></div></div></div><div class="gmail_default"><font face="arial, sans-serif"><br></font></div><div class="gmail_default"><font face="arial, sans-serif"><br></font></div><div class="gmail_default"><div><font face="arial, sans-serif"><b>Title: </b> Local Algorithms for Sparse Connected Subgraphs</font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b>Abstract: </b>Consider a setting in which inputs to and outputs from a computational problem are so large, that there is not time to read them in their entirety. However, if one is only interested in small parts of the output at any given time, is it really necessary to solve the entire computational problem? Is it even necessary to view the whole input? We survey recent work in the model of "local computation algorithms" which for a given input, supports queries by a user to values of specified bits of a legal output. The goal is to design local computation algorithms in such a way that very little of the input needs to be seen in order to determine the value of any single bit of the output. In this talk, we survey a series of results on local computation algorithms for finding sparse connected subgraphs and sparse spanners.</font></div><p class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_-5680779581752768105inbox-inbox-m_2981149214989969629inbox-inbox-p1" style="color:rgb(33,33,33)"><font face="arial, sans-serif"><b>Host:</b> <a href="mailto:avrim@ttic.edu" target="_blank">Avrim Blum</a><br></font></p><p class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_-5680779581752768105inbox-inbox-m_2981149214989969629inbox-inbox-p1" style="color:rgb(33,33,33)"><span style="color:rgb(34,34,34);font-kerning:none"><font style="vertical-align:inherit"><font face="arial, sans-serif" style="vertical-align:inherit"><br></font></font></span></p><p class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_-5680779581752768105inbox-inbox-m_2981149214989969629inbox-inbox-p1" style="color:rgb(33,33,33)"><font face="arial, sans-serif"><span style="color:rgb(34,34,34);font-kerning:none"><font style="vertical-align:inherit"><font style="vertical-align:inherit">For more information on the </font></font><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-m_37711595404184628gmail-m_-8366621373355229216gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-il"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-il"><span class="gmail-m_5482748634321315606gmail-il">colloquium</span></span></span></span></font></font></span></span></span></span></span></span></span><font style="vertical-align:inherit"><font style="vertical-align:inherit"> series or to subscribe to the mailing list,please </font></font></span><font style="color:rgb(34,34,34);vertical-align:inherit"><font style="vertical-align:inherit">see </font></font><a href="http://www.ttic.edu/colloquium.php" target="_blank"><font style="vertical-align:inherit"><font style="vertical-align:inherit">http://www.</font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">ttic.edu/</font></font><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-il"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-il"><span class="gmail-m_5482748634321315606gmail-il">colloquium</span></span></span></span></font></font></span></span></span></span></span></span><font style="vertical-align:inherit"><font style="vertical-align:inherit">.php</font></font></a><span style="color:rgb(34,34,34)"> </span><br></font></p></div><br class="gmail-Apple-interchange-newline"></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, May 13, 2019 at 4:17 PM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div style="font-size:small"><div><div><p class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_5987474974647831651gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_9103776001042077600gmail-p1" style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><b><font style="vertical-align:inherit"><font style="vertical-align:inherit">When: </font></font></b><font style="vertical-align:inherit"><font style="vertical-align:inherit"> Monday, May 20th at <b>11:00 am</b></font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b><font style="vertical-align:inherit"><font style="vertical-align:inherit">Where: </font></font></b><font style="vertical-align:inherit"><font style="vertical-align:inherit">TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b></font></font>Ronitt Rubinfeld, MIT and Tel Aviv University</font></p></div></div></div><div style="font-size:small"><font face="arial, sans-serif"><br></font></div><div style="font-size:small"><font face="arial, sans-serif"><br></font></div><div><div style="font-size:small"><font face="arial, sans-serif"><b>Title: </b> Local Algorithms for Sparse Connected Subgraphs</font></div><div style="font-size:small"><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b style="font-size:small">Abstract: </b>Consider a setting in which inputs to and outputs from a
computational problem are so large, that there is not time to read them in their entirety. However, if one is only interested in small
parts of the output at any given time, is it really necessary to solve the
entire computational problem? Is it even necessary to view the whole input? We
survey recent work in the model of
"local computation algorithms" which for a given input,
supports queries by a user to values of specified
bits of a legal output. The goal is to
design local computation algorithms in such a way that very little of the input
needs to be seen in order to determine the value of any single bit of the
output. In this talk, we survey a series of results on local computation
algorithms for finding sparse connected subgraphs and sparse spanners.</font></div><p class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_-5680779581752768105inbox-inbox-m_2981149214989969629inbox-inbox-p1" style="font-size:small;color:rgb(33,33,33)"><font face="arial, sans-serif"><b>Host:</b> <a href="mailto:avrim@ttic.edu" target="_blank">Avrim Blum</a><br></font></p><p class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_-5680779581752768105inbox-inbox-m_2981149214989969629inbox-inbox-p1" style="font-size:small;color:rgb(33,33,33)"><span style="color:rgb(34,34,34);font-kerning:none"><font style="vertical-align:inherit"><font style="vertical-align:inherit" face="arial, sans-serif"><br></font></font></span></p><p class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_-5680779581752768105inbox-inbox-m_2981149214989969629inbox-inbox-p1" style="font-size:small;color:rgb(33,33,33)"><font face="arial, sans-serif"><span style="color:rgb(34,34,34);font-kerning:none"><font style="vertical-align:inherit"><font style="vertical-align:inherit">For more information on the </font></font><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-m_37711595404184628gmail-m_-8366621373355229216gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-il"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-il"><span class="gmail-m_5482748634321315606gmail-il">colloquium</span></span></span></span></font></font></span></span></span></span></span></span></span><font style="vertical-align:inherit"><font style="vertical-align:inherit"> series or to subscribe to the mailing list,please </font></font></span><font style="color:rgb(34,34,34);vertical-align:inherit"><font style="vertical-align:inherit">see </font></font><a href="http://www.ttic.edu/colloquium.php" target="_blank"><font style="vertical-align:inherit"><font style="vertical-align:inherit">http://www.</font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">ttic.edu/</font></font><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-m_-5864378453105999086gmail-m_-1690647303496242289m_1430452980776983890gmail-m_1031910664862358996gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-m_767208242022040581gmail-m_5118066322451693210gmail-m_3292142122556441362m_4179300188985034065m_8112548636363365103gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-m_-2053129909387779305gmail-m_-4421783803009889794gmail-m_1235227957090907765gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-m_3914652650996472955gmail-m_-4783362384882292594m_6961031835771836416gmail-m_3149180880964055314gmail-m_5803000941478265060gmail-m_3739772758111120207gmail-m_-4374496420704574181gmail-m_-8232014986225864746gmail-m_2118555233517397122gmail-m_-6347337869693432729gmail-m_6770742588603738482gmail-m_3034006998144763397gmail-m_-2909309711111506553gmail-m_3361278369988668236gmail-m_3239492643088026663gmail-il"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-m_-7670275615116031415gmail-m_-5817829815640557222gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-m_4614845926281015477gmail-m_6041720643954058195gmail-il"><span class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-il"><span class="gmail-m_5482748634321315606gmail-il">colloquium</span></span></span></span></font></font></span></span></span></span></span></span><font style="vertical-align:inherit"><font style="vertical-align:inherit">.php</font></font></a><span style="color:rgb(34,34,34)"> </span><br></font></p><br class="gmail-m_5482748634321315606gmail-m_417349372124497387gmail-Apple-interchange-newline"></div><br class="gmail-m_5482748634321315606gmail-Apple-interchange-newline"></div><div><div dir="ltr" class="gmail-m_5482748634321315606gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>
</blockquote></div></div>