Hamming distance completeness and sparse matrix multiplication

Daniel Graf, Karim Labib, Przemysław Uznański

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 Hamm…