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

Speaker: 
Н. Карпов
Date: 
Monday, December 5, 2016 - 14:00
Place: 
106
Abstract: 

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