Новости из мира науки: матрицы размера

теперь умеют умножать за

. Другими словами, доказано, что

, где

—
экспонента умножения матриц. Доказала это совсем недавно
Вирджиния Василевска-Вильямс, улучшив тем самым оценку

, полученную Копперсмитом и Виноградом в 1987 году. Я напишу про важность этого алгоритма совсем немножко. Тем, кому интересно узнать побольше, предлагается почитать посты
Скотта Ааронсона,
Ричарда Липтона и
Билла Гасарша.
Итак, многие теоретические верхние оценки на время работы алгоритмов используют экспоненту умножения матриц. В частности, много алгоритмов на графах эксплуатируют данную идею: если A — матрица смежности графа, то

— количество (не обязательно простых!) путей длины k между вершинами i и j. Эта простая идея позволяет за время

проверить, есть ли в графе треугольник (3-клика): нужно возвести матрицу смежности в куб (для этого потребуется два умножения матриц) и посмотреть на диагональ. Отметим, что речь здесь именно о теоретических оценках, поскольку продвинутые алгоритмы умножения матриц хоть и обгоняют асимптотически простой кубический алгоритм, но на практике дают ускорение только на огромных размерах матриц.
Ещё несколько примеров: