Мы рассмотрим задачу Orthogonal Vectors, в которой дано множество из n d-мерных булевых векторов и необходимо определить, есть ли среди этого множества два вектора ортогональных друг другу. Существует гипотеза (Orthogonal Vector Conjecture, OVC), что при d порядка log(n) любой алгоритм для данной задачи работает за время $n^{2-o(1)}$. В предположении данной гипотезы уже доказаны нижние оценки для многих других задач из класса P, например, для задач Edit Distance и Longest Common Subsequence.

Мы покажем, что OVC верна в некоторых вычислительных моделях, а именно для вычисления OV требуется формула (с любым базисом, с константной входящей степенью в вершинах) и ветвящаяся программа квадратичного размера. Данная нижняя оценка совпадает с лучшими известными нижними оценками для явных функций в данных моделях.

Доклад по статье The Orthogonal Vectors Conjecture for Branching Programs and Formulas авторов Daniel Kane и Ryan Williams.