Our main contribution lies in designing a mechanism that reduces an instance of Subset Sum to several simpler instances, each with some special structure, and keeps track of interactions between them. This allows us to combine techniques from approximation algorithms, pseudo-polynomial algorithms, and additive combinatorics.
We also prove several related results. Notably, we improve approximation schemes for 3-SUM, (min,+)-convolution, and Tree Sparsity. Finally, we argue why breaking the quadratic barrier for approximate Knapsack is unlikely by giving an Ω((n + 1/ε)^{2−o(1)}) conditional lower bound.