<div dir="ltr"><div class="gmail_default" style=""><div class="gmail_default" style=""><font color="#000000" face="georgia, serif" style=""><b style="">When:</b>         Friday, May 12th<b style=""> at <span style="background-color:rgb(255,255,0)">12:30pm CT  </span></b></font><div dir="ltr" style=""><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font color="#000000" face="georgia, serif"> <br><b>Where:</b><b>  </b>      Talk will be given<span style="background-color:rgb(255,255,0)"> </span><span style="background-color:rgb(255,255,0)"><font style="font-weight:bold"><u>live, in-person</u></font><font style="font-weight:bold"> </font></span>at</font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font color="#000000" face="georgia, serif">                       TTIC, 6045 S. Kenwood Avenue</font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font color="#000000" face="georgia, serif">                        5th Floor, Room 530<b>              </b>   </font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font color="#000000" face="georgia, serif"><br></font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="georgia, serif" color="#000000"><b><span class="gmail_default"></span>Virtually:</b>     via Panopto (<a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=ec243af6-1ad5-4610-bc35-af1901007029" target="_blank">Livestream</a>) </font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font color="#000000" face="georgia, serif"> </font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font color="#000000" face="georgia, serif" style=""><b style="">Who:</b><b style=""> </b>          Yury </font><font face="georgia, serif">Makarychev<span style="color:rgb(0,0,0)">, TTIC</span></font></p><table border="0" cellspacing="0" cellpadding="0" width="0" style="width:0in;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;border-collapse:collapse"><tbody><tr><td style="padding:0in"></td></tr></tbody></table><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font color="#000000" face="georgia, serif" style=""> <span class="gmail_default"></span></font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="georgia, serif"><font color="#000000"><b style="">T</b><b>itle:</b><b> </b>          </font>Higher-Order Cheeger Inequality for Partitioning with Buffers</font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="georgia, serif"><br></font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="georgia, serif" style=""><b style="">Abstract:  </b> We prove a new generalization of the higher-order Cheeger inequality for partitioning with buffers. Consider a graph G. The buffered expansion of a set of vertices S with a buffer B is the edge expansion of S after removing all the edges from S to its buffer B. An ε-buffered k-partitioning of graph G is a partitioning of G into disjoint components P_1, ..., P_k and buffers B_1, ..., B_k in which the size of buffer B_i is at most ε|P_i|. We prove that there exists an ε-buffered k-partitioning of G, in which the buffered expansion of each P_i with buffer B_i is at most O_𝛿((log k) / ε) λ_{k'}, where where λ_{k'} is the k'-th smallest eigenvalue of the normalized Laplacian of G and k' = (1 + 𝛿) k.<br><br>Our inequality is constructive and avoids the “square-root loss” that is present in the standard Cheeger inequalities (even for k=2). We also provide a complementary lower bound, and a generalization to the setting with arbitrary vertex weights and edge costs. Moreover our result implies and generalizes the standard higher-order Cheeger inequalities and another recent Cheeger-type inequality by Kwok, Lau, and Lee (2017) involving robust vertex expansion.<br><br>Joint work with Konstantin Makarychev, Liren Shan, and Aravindan Vijayaraghavan<br></font></p><p class="MsoNormal" style="font-size:small;font-family:Arial,Helvetica,sans-serif;margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="georgia, serif"><br></font></p><p class="MsoNormal" style="font-size:small;font-family:Arial,Helvetica,sans-serif;margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><div class="gmail_default" style="font-size:small;font-family:Arial,Helvetica,sans-serif"><div dir="ltr"><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b><font color="#000000" face="georgia, serif">*********************************************************************************************</font></b></p><p class="MsoNormal" style="margin:0in 0in 8pt;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;line-height:15.6933px"><font face="georgia, serif" color="#000000"><b>Masks are optional in all common areas. </b><b>Full visitor guidance is available at <a href="http://ttic.edu/visitors" target="_blank">ttic.edu/visitors</a>.</b></font></p><p class="MsoNormal" style="margin:0in 0in 12pt;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;line-height:15.6933px"><b><font color="#000000" face="georgia, serif">*********************************************************************************************</font></b></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b><i><font color="#000000" face="georgia, serif">Research at TTIC Seminar Series</font></i></b></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font color="#000000" face="georgia, serif"> </font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font color="#000000" face="georgia, serif">TTIC is hosting a weekly seminar series presenting the research currently underway at the Institute. Every week a different TTIC faculty member will present their research.  The lectures are intended for students seeking research topics and advisors and for the general TTIC and University of Chicago communities interested in hearing what their colleagues are up to.</font></p></div></div></div></div><div style="font-size:small;font-family:Arial,Helvetica,sans-serif"><br></div><div style="font-size:small;font-family:Arial,Helvetica,sans-serif"><br></div></div><div><br></div><span class="gmail_signature_prefix">-- </span><br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><b style="background-color:rgb(255,255,255)"><font color="#3d85c6">Brandie Jones </font></b><div><div><div><font color="#3d85c6"><b><i>Executive </i></b></font><b style="color:rgb(61,133,198)"><i>Administrative Assistant</i></b></div></div><div><span style="background-color:rgb(255,255,255)"><font color="#3d85c6">Toyota Technological Institute</font></span></div><div><span style="background-color:rgb(255,255,255)"><font color="#3d85c6">6045 S. Kenwood Avenue</font></span></div><div><span style="background-color:rgb(255,255,255)"><font color="#3d85c6">Chicago, IL  60637</font></span></div></div><div><span style="background-color:rgb(255,255,255)"><font color="#3d85c6"><a href="http://www.ttic.edu" target="_blank">www.ttic.edu</a> </font></span></div><div><font color="#3d85c6"><div style="background-color:rgb(238,238,238)"><div style="color:rgb(32,33,36)"><span style="color:rgb(61,133,198)">Working Remotely on Tuesdays</span></div></div></font></div></div></div></div>