Although I'm not an expert in the area, I dare say that this is a afntastic result.
Amir offered two motivations for the study of this specific problem. The first is the identification of prpoblems that have so far resisted classification into an easy (e.g., linear time) vs hard (e.g., traingle-hard) dichotomy (of fine grained complexity). The second is a classification of (induced) subgraph-freeness problems, and specifically $O(n^2)$-time vs $k$-clique-hardness for $k\geq 3$.
Recalling that for every $h$-vertex graph $H$ it holds that induced $H$-freeness is (fine grained) reducible to $K_h$-freeness, the question is whether for every $H$ there exists a $k\leq h$ such that induced $H$-freeness is (fine grained) equivalent to $K_k$-freeness. The 4-cycle is unique in that it is the only graph $H$ for which it was not known that induced $H$-freeness is either solvable in $O(n^2)$ time or is triangle-hard. Assuming that detecting triangles has no $n^{3-Omega(1)}$-time algorithm, the current work rules out the second possibility.
In this paper, we present the first truly subcubic, combinatorial algorithm for detecting an induced 4-cycle in a graph. The running time is O(n^{2.84}) on n-node graphs, thus separating the task of detecting induced 4-cycles from detecting triangles, which requires n^{3-o(1)} time combinatorially under the popular Boolean Matrix Multiplication hypothesis.
Significant work has gone into characterizing the exact time complexity of induced H-detection, relative to the complexity of detecting cliques of various sizes. Prior work identified the question of whether induced 4-cycle detection is triangle-hard as the only remaining case towards completing the lowest level of the classification, dubbing it a curious case [Dalirrooyfard, Vassilevska W., FOCS 2022]. Our result can be seen as a negative resolution of this question.
Our algorithm deviates from previous techniques in the large body of subgraph detection algorithms and employs the trendy topic of graph decomposition that has hitherto been restricted to more global problems (as in the use of expander decompositions for flow problems) or to shaving subpolynomial factors (as in the application of graph regularity lemmas). While our algorithm is slower than the (non-combinatorial) state-of-the-art O(n^{\omega})-time algorithm based on polynomial identity testing [Vassilevska W., Wang, Williams, Yu, SODA 2014], combinatorial advancements often come with other benefits. In particular, we give the first nontrivial deterministic algorithm for detecting induced 4-cycles.