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