Recently, Anthropic announced truly subquadratic and subcubic algorithms for 3SUM and all‑pairs shortest paths (APSP). Those results relied on a new subroutine for rectangular matrix multiplication with selected output entries, built by adapting the classic techniques of Schönhage (1981) and Coppersmith (1982).\ \ This note presents three related contributions:\
- A different truly subquadratic randomized algorithm for integer 3SUM. It completely avoids matrix multiplication and instead modifies the dynamic‑programming implementations of subset convolution and the zeta transform, using only simple inclusion‑exclusion subtraction tricks (no fast Fourier transform needed). The whole solution fits in about five pages.\
- Extending the same approach to odd constant $k$, we obtain a randomized algorithm for $k$‑SUM on integers with running time $O\bigl(n^{\lceil k/2\rceil-\varepsilon_k}\bigr)$ for some constant $\varepsilon_k>0$, thereby refuting the $k$‑SUM hypothesis for all odd $k$.\
- Prior reductions from 3SUM and APSP to selected‑entry rectangular matrix multiplication were randomized for real‑valued inputs. We give new deterministic reductions, yielding a truly subquadratic deterministic algorithm for Real 3SUM and a truly subcubic deterministic algorithm for Real APSP.\ \ Review