Several recent works have studied dimension-reduction (sketching) for special cases of symmetric norms such as the Orlicz norm [1]}, [2]}, [3]}, for various numerical linear algebra primitives [4]}. These sketching techniques are quite ad-hoc and are carefully tailored to the norm in question. It is therefore natural to ask whether symmetry alone is enough to guarantee dimensionality-reduction for symmetric similarity search, in other words
