  We show that a broad class of $(+,\diamond)$ vector products (for binary
integer functions $\diamond$) are equivalent under one-to-polylog reductions to
the computation of the Hamming distance. Examples include: the dominance
product, the threshold product and $\ell_{2p+1}$ distances for constant $p$.
Our results imply equivalence (up to polylog factors) between complexity of
computation of All Pairs: Hamming Distances, $\ell_{2p+1}$ Distances, Dominance
Products and Threshold Products. As a consequence, Yuster's~(SODA'09) algorithm
improves not only Matou\v{s}ek's (IPL'91), but also the results of Indyk,
Lewenstein, Lipsky and Porat (ICALP'04) and Min, Kao and Zhu (COCOON'09).
Furthermore, our reductions apply to the pattern matching setting, showing
equivalence (up to polylog factors) between pattern matching under Hamming
Distance, $\ell_{2p+1}$ Distance, Dominance Product and Threshold Product, with
current best upperbounds due to results of Abrahamson (SICOMP'87), Amir and
Farach (Ann.~Math.~Artif.~Intell.'91), Atallah and Duket (IPL'11), Clifford,
Clifford and Iliopoulous (CPM'05) and Amir, Lipsky, Porat and Umanski (CPM'05).
The resulting algorithms for $\ell_{2p+1}$ Pattern Matching and All Pairs
$\ell_{2p+1}$, for $2p+1 = 3,5,7,\dots$ are new.
  Additionally, we show that the complexity of AllPairsHammingDistances (and
thus of other aforementioned AllPairs- problems) is within polylog from the
time it takes to multiply matrices $n \times (n\cdot d)$ and $(n\cdot d) \times
n$, each with $(n\cdot d)$ non-zero entries. This means that the current
upperbounds by Yuster (SODA'09) cannot be improved without improving the sparse
matrix multiplication algorithm by Yuster and Zwick~(ACM TALG'05) and vice
versa.
