论文标题
单色三角形，中间基质产品和卷积
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions
论文作者
论文摘要
研究最多的线性代数操作，矩阵乘法，具有出人意料的快速$ o（n^ω）$ time算法，$ω<2.373 $。另一方面，$（\ min，+）$矩阵产品是许多基本图形问题（例如APSP）的核心，仅在其蛮力立方运行时间中获得了较小的改进，并且被广泛猜想以要求$ n^{3-o（1）} $时间。有很多基质产品和图形问题，其复杂性似乎位于这两个问题的中间。例如，最小见证矩阵产品，有向未加权图的APSP的最小见证矩阵产品，并确定边缘色图是否包含单色三角形，都可以在$ \ tilde o（n^{（3+ω）/2}）中求解。卷积问题发生了类似的现象，可以在$ \ tilde o（n^{1.5}）$时间中解决类似的中间问题。 在矩阵产品或卷积世界中，可以改善这些中间问题的运行时间吗？或者，或者，一个人可以以有意义的方式将这些问题与其他关键问题联系起来？ 本文通过提供细粒度减少网络来取得这些问题的进展。例如，我们表明的是，在有向的未加权图中的APSP可以将最小见证产品减少到Min-Max产品和单色三角形问题的变体。我们还表明，单色三角形的自然卷积变体与著名的3sum问题相当。由于该变体可在$ o（n^{1.5}）$ time中溶解，而3sum则在$ O（n^2）$ time中（并且可以猜想需要$ n^{2-o（1）$ time），因此我们的结果给出了不同运行时间的自然问题之间的第一个细粒度。
The most studied linear algebraic operation, matrix multiplication, has surprisingly fast $O(n^ω)$ time algorithms for $ω<2.373$. On the other hand, the $(\min,+)$ matrix product which is at the heart of many fundamental graph problems such as APSP, has received only minor improvements over its brute-force cubic running time and is widely conjectured to require $n^{3-o(1)}$ time. There is a plethora of matrix products and graph problems whose complexity seems to lie in the middle of these two problems. For instance, the Min-Max matrix product, the Minimum Witness matrix product, APSP in directed unweighted graphs and determining whether an edge-colored graph contains a monochromatic triangle, can all be solved in $\tilde O(n^{(3+ω)/2})$ time. A similar phenomenon occurs for convolution problems, where analogous intermediate problems can be solved in $\tilde O(n^{1.5})$ time. Can one improve upon the running times for these intermediate problems, in either the matrix product or the convolution world? Or, alternatively, can one relate these problems to each other and to other key problems in a meaningful way? This paper makes progress on these questions by providing a network of fine-grained reductions. We show for instance that APSP in directed unweighted graphs and Minimum Witness product can be reduced to both the Min-Max product and a variant of the monochromatic triangle problem. We also show that a natural convolution variant of monochromatic triangle is fine-grained equivalent to the famous 3SUM problem. As this variant is solvable in $O(n^{1.5})$ time and 3SUM is in $O(n^2)$ time (and is conjectured to require $n^{2-o(1)}$ time), our result gives the first fine-grained equivalence between natural problems of different running times.
