Понедельник 05.12. Н. Карпов: "Решение задачи 3-SUM с малой памятью и с малой глубиной дерева"

Понедельник 05.12. Н. Карпов: "Решение задачи 3-SUM с малой памятью и с малой глубиной дерева"

Date:

Monday, December 5, 2016 - 14:00

Abstract:

На семинаре мы рассмотрим алгоритм для задачи 3-SUM с малым количеством дополнительной памяти (примерно корень из n) и его обобщение на случай задачи k-SUM. Мы покажем почему это влечет ослабление 3-SUM гипотезы. Вдобавок, мы рассмотрим нетривиальное дерево решений глубины примерно n^1.5, где в каждом узле решение принимается на основе знака линейной комбинации константного набора входных чисел.