אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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).