Пятница, 16 ноября, ауд. 106. Начало в 14:00.
Докладчик: Людмила Глинских.
Тема: Нижняя оценка на размер ветвящихся программ и формул для задачи Orthogonal Vectors.
Abstract
Мы рассмотрим задачу Orthogonal Vectors, в которой дано множество из n d-мерных булевых векторов и необходимо определить, есть ли среди этого множества два вектора ортогональных друг другу. Существует гипотеза (Orthogonal Vector Conjecture, OVC), что при d порядка log(n) любой алгоритм для данной задачи работает за время
![$ n^{2-o(1)} $](/sites/default/files/tex/842a9a154f55aa4c4a8db4441b1741053aa3e397.png)
. В предположении данной гипотезы уже доказаны нижние оценки для многих других задач из класса P, например, для задач Edit Distance и Longest Common Subsequence.
Мы покажем, что OVC верна в некоторых вычислительных моделях, а именно для вычисления OV требуется формула (с любым базисом, с константной входящей степенью в вершинах) и ветвящаяся программа квадратичного размера. Данная нижняя оценка совпадает с лучшими известными нижними оценками для явных функций в данных моделях.
Доклад по статье The Orthogonal Vectors Conjecture for Branching Programs and Formulas авторов Daniel Kane и Ryan Williams.