Home

Пятница 16.11. Людмила Глинских: "Нижняя оценка на размер ветвящихся программ и формул для задачи Orthogonal Vectors"

Пятница, 16 ноября, ауд. 106. Начало в 14:00.

Докладчик: Людмила Глинских.

Тема: Нижняя оценка на размер ветвящихся программ и формул для задачи Orthogonal Vectors.

Abstract

Мы рассмотрим задачу 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.