Понедельник, 5 декабря, 106. Начало в 14:00.
Докладчик: Н. Карпов.
Тема: Решение задачи 3-SUM с малой памятью и с малой глубиной дерева.
Abstract
На семинаре мы рассмотрим алгоритм для задачи 3-SUM с малым количеством дополнительной памяти (примерно корень из n) и его обобщение на случай задачи k-SUM. Мы покажем почему это влечет ослабление 3-SUM гипотезы. Вдобавок, мы рассмотрим нетривиальное дерево решений глубины примерно n^1.5, где в каждом узле решение принимается на основе знака линейной комбинации константного набора входных чисел.
