November 29th, 2011

moose, transparent

наука не стоит на месте

(это будет интересно только программистам/компьютерщикам, зато они-то визжать будут от восторга)

Скотт Ааронсон рассказал потрясающее. Как вы помните, уже 20 лет лучший алгоритм для умножения двух матриц n x n делает эту неблагодарную работу за время O(n2.376) - результат Копперсмита и Винограда. Так вот, появилась новая статья, в которой эта верхняя граница снижена - до O(n2.373)!!!

Все подробности в этой статье (в ее введении есть также полезный обзор всей истории алгоритмов умножения матриц). Я сегодня, подозреваю, уснуть не смогу от возбуждения...