One formulation of the 3-SUM problem is determining whether a set of $$$n$$$ integers has a subset of $$$3$$$ integers that add up to zero. With hashing, this takes $$$O(n^2)$$$ time and was conjectured to be optimal.

The all-pairs shortest paths problem (APSP) is determining the shortest path between all pairs of vertices in a graph with $$$n$$$ vertices. Floyd-Warshall uses $$$O(n^3)$$$ time and was conjectured to be optimal.

It seems possible that neither of these conjectures is true, declared by the paper https://arxiv.org/pdf/2610.06783 using an internal model of Claude and verified using Lean.