[Theory] TODAY: [TTIC Talks] 5/12 Research at TTIC: Yury Makarychev, TTIC

[Brandie Jones]

*When:*         Friday, May 12th* at 12:30pm CT  *


*Where:*        Talk will be given *live, in-person* at

                       TTIC, 6045 S. Kenwood Avenue

                        5th Floor, Room 530


*Virtually:*     via Panopto (Livestream
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=ec243af6-1ad5-4610-bc35-af1901007029>
)



*Who:*           Yury Makarychev, TTIC



*T**itle:*           Higher-Order Cheeger Inequality for Partitioning with
Buffers


*Abstract:  * 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.

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.

Joint work with Konstantin Makarychev, Liren Shan, and Aravindan
Vijayaraghavan



***********************************************************************************************

*Masks are optional in all common areas. **Full visitor guidance is
available at ttic.edu/visitors <http://ttic.edu/visitors>.*

***********************************************************************************************

*Research at TTIC Seminar Series*



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

-- 
*Brandie Jones *
*Executive **Administrative Assistant*
Toyota Technological Institute
6045 S. Kenwood Avenue
Chicago, IL  60637
www.ttic.edu
Working Remotely on Tuesdays
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230512/73aa0558/attachment.html>