Search Mailing List Archives
[theory-seminar] Theory Lunch 6/2: Seri Khoury (Berkeley)
junyaoz at stanford.edu
Sun May 29 21:08:12 PDT 2022
This week's theory lunch will take place Thursday at noon in the Engineering Quad<https://www.google.com/maps/place/Science+%26+Engineering+Quad+Courtyardfirstname.lastname@example.org,-122.1765394,17z/data=!3m1!4b1!4m5!3m4!1s0x808fbb8ce58bcc27:0x677c06a883bb7bb7!8m2!3d37.428484!4d-122.1743507>. We'll start with some socializing, followed by a talk at 12:30pm. Seri will tell us about: Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond
Abstract: Triangle finding is at the base of many conditional lower bounds in P, mainly for distance computation problems, and the existence of many $4$- or $5$-cycles in a worst-case instance had been the obstacle towards resolving major open questions.
We present a new technique for efficiently removing almost all short cycles in a graph without unintentionally removing its triangles. Consequently, triangle finding problems do not become easy even in almost $k$-cycle free graphs, for any constant $k\geq 4$. This allows us to establish new hardness of approximation results for distance related problems, and new hardness results for k-cycle finding problems.
In this talk, I will explain the short cycle removal technique and its consequences for approximate distance oracles, k-cycle detection, and more.
Based on a joint work with Amir Abboud, Karl Bringmann, and Or Zamir (to appear in STOC 2022).
BTW, I'm looking for volunteers to take over organizing theory lunch (starting from summer quarter). If you are interested, please let me know.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar