Seri's presentation was fascinating. He focused on the hardness of constructing constant-factor distance approximation oracle in almost linear time. The proof is via a reduction from the problem of finding all edges that are included in a triangle. The reduction proceeds in two steps, where the second step is sampling a random induced subgraph in which each vertex is included with probability $p$ (set to $n sup {0.5-eps}$). This works well (wrt eliminating all 4-cycles while preserving a triangle with noticeable probability), provided that the number of 4-cycles is sub-quadratic in $n$, and the first step makes sure that this is the case. The first step is based on the observation that if a graph with degree bound $sqrt(n)$ has too many 4-cycles, then one can find a (relatively small) dense subgraph in it.
Needless to say, the above overview pushes many issues under the carpet, and this refers only to the case of $k=4$, whereas the paper handles any consatnt $k geq 4$ (as described in the following abstract).
To the the relevance of getting rid of 4-cycles, note that an edge appears on a triangle if and only if the distance between its endpoints (in the graph that is obtained by omitting this edge) is two. But if this distance is not two and the original graph has no 4-cycles, then the distance is at least four. Similarly if there are no k-cycles for every $k\in[4,K]$, then the distance in the residual graph is at least K. Hence, the existence of a traiangle is reduced to approximating the distance between vertices in an auxiliary graph.
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.
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.
Hardness of approximation: Are there distance oracles with $m sup {1+o(1)}$ preprocessing time and $m sup o(1)$ query time that achieve a constant approximation? Existing algorithms with such desirable time bounds only achieve super-constant approximation factors, while only 3-eps factors were conditionally ruled out (Patrascu, Roditty, and Thorup; FOCS 2012). We prove that no O(1) approximations are possible, assuming the 3-SUM or APSP conjectures. In particular, we prove that k-approximations require $Omega(m sup {1+1/ck})$ time, which is tight up to the constant c. The lower bound holds even for the offline version where we are given the queries in advance, and extends to other problems such as dynamic shortest paths.
The 4-Cycle problem: An infamous open question in fine-grained complexity is to establish any surprising consequences from a subquadratic or even linear-time algorithm for detecting a 4-cycle in a graph. We prove that $Omega(m sup 1.1194)$ time is needed for k-cycle detection for all k geq 4, unless we can detect a triangle in $sqrt(n)$-degree graphs in $O(n sup {2-eps})$ time; a breakthrough that is not known to follow even from optimal matrix multiplication algorithms.
Available from ArXiv 2204.10465.