Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond
event speaker icon
Seri Khoury (UC Berkeley)
event date icon
Wednesday, 10.08.2022, 12:30
event location icon
Amado 814
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, such as distance oracles, dynamic shortest paths, and more. Based on a joint work with Amir Abboud, Karl Bringmann, and Or Zamir (STOC 2022).