опубликовал препринт статьи “A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications”. Это довольно удивительный теоретический результат, где существенно ускоряется то, что интуитивно ускоряться не должно: поиск треугольника в графе. Как модно в последние годы, алгоритм вероятностный, но это не мешает порушить сразу несколько гипотез, на которых полагалась куча статей:
- the O(n^7/3) runtime surpasses the long-standing fastest algorithm for triangle detection based on matrix multiplication running in O(n^ω)=O(n^2.372) time, due to Itai and Rodeh (1978).
- the O(m^4/3) runtime surpasses the long-standing fastest algorithm for triangle detection in sparse graphs based on matrix multiplication running in O(m^2ω/(ω+1))=O(m^1.407) time due to Alon, Yuster, and Zwick (1997).
- the O(n^7/3) time algorithm for triangle detection leads to a O(n^(25/9)logn) time combinatorial algorithm for n×n Boolean matrix multiplication, by a reduction of V. V. Williams and R. R. Williams (2018).This invalidates a conjecture of A. Abboud and V. V. Williams (FOCS 2014).
- the O(m^4/3) runtime invalidates a conjecture of A. Abboud and V. V. Williams (FOCS 2014) that any combinatorial algorithm for triangle detection requires m3/2−o(1) time.
- as a direct application of the triangle detection algorithm, we obtain a faster exact algorithm for the k-clique problem, surpassing an almost 40 years old algorithm of Nešetřil and Poljak (1985). This result strongly disproves the combinatorial k-clique conjecture.
- as another direct application of the triangle detection algorithm, we obtain a faster exact algorithm for the Max-Cut problem, surpassing an almost 20 years old algorithm of R. R. Williams (2005).
Если результат подтвердится, существенно подвинутся по сложности алгоритмы, которые основаны на булевом перемножении матриц. Запасаемся попкорном на следующие FOCS/STOC. 🍿
EDIT: похоже, в статье всё-таки есть проблемы, прекрасного будущего не ожидается. 😟