Minimal number of additions in convolution
One method which attracted my attention recently is Discrete Time Random Sampling.

Which is an approximation method useful to reduce both multiplications and additions in filtering. 

Filter and $N$-length signal by a $L$-length filter can be performed in $\mathcal{O}(LM)$  instead of  $\mathcal{O}(LN)$. Where $M\ll N$. 
Which is done by picking samples at random in a way described in the paper.

See also Frequency-Shaped Randomized Sampling for a more sophisticated approach which allows you to shape the spectrum of the error.