  In this work, we show deep connections between Locality Sensitive Hashability
and submodular analysis. We show that the LSHablility of the most commonly
analyzed set similarities is in one-to-one correspondance with the
supermodularity of these similarities when taken with respect to the symmetric
difference of their arguments. We find that the supermodularity of equivalent
LSHable similarities can be dependent on the set encoding. While monotonicity
and supermodularity does not imply the metric condition necessary for
supermodularity, this condition is guaranteed for the more restricted class of
supermodular Hamming similarities that we introduce. We show moreover that LSH
preserving transformations are also supermodular-preserving, yielding a way to
generate families of similarities both LSHable and supermodular. Finally, we
show that even the more restricted family of cardinality-based supermodular
Hamming similarities presents promising aspects for the study of the link
between LSHability and supermodularity. We hope that the several bridges that
we introduce between LSHability and supermodularity paves the way to a better
understanding both of supermodular analysis and LSHability, notably in the
context of large-scale supermodular optimization.
