Most of our lower bounds rely on the following theorem, which establishes hardness of a triangle finding problem based on either of the standard conjectures about 3-SUM or All Pairs Shortest Paths (for background on these conjectures see e.g. [1]}, [2]}).
