2 problems

The 3SUM problem asks whether, given $n$ integers from $\{-n^4,\ldots,+n^4\}$, there is a triple satisfying the 3SUM condition. 3SUM conjecture. The 3SUM problem on $n$ such intege…

Let $f:{0,1}^{2n}\to\{\pm1\}$, and consider the Multiphase Problem in which $m$ vectors $S_1,\ldots,S_m\in\{0,1\}^n$ are preprocessed, an update vector $X\in\{0,1\}^n$ modifies the…