5 октября американские исследователи Вирджиния Василевска-Уильямс, известная своими быстрыми (и безумно сложными) алгоритмами перемножения матриц за вместо и её бывший аспирант Джош Алман опубликовали препринт на arxiv.org, демонстрирующий ...
5 октября американские исследователи Вирджиния Василевска-Уильямс, известная своими быстрыми (и безумно сложными) алгоритмами перемножения матриц за вместо и её бывший аспирант Джош Алман опубликовали препринт на arxiv.org, демонстрирующий алгоритм решения задачи 3SUM за .
Это знаковое событие в узких кругах. Во-первых, раньше предполагалось, что решить эту задачу быстрее, чем за , невозможно. Во-вторых, вместе с ней наконец решилась быстрее, чем за , задача нахождения кратчайших путей между любыми парами вершин в графе (All-Pairs Shortest Paths, APSP) — по-настоящему практическая задача вычислительной геометрии. В-третьих, мало того, что корректность работы проверяла закрытая модель Anthropic — авторы также утверждают, что Claude нашёл изначальный алгоритм, после чего учёные осознали и улучшили его.
В этой новости я очень кратко перескажу долгий путь, который привёл к этому открытию, и опишу роль LLM в финале этого пути.