2026-09-10T09:44:59Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:27776 2026-09-09T12:19:38Z ddc:004 open_access
On the LSH Distortion of Ulam and Cayley Similarities Chierichetti, Flavio Giacchini, Mirko Kumar, Ravi Tani, Erasmo Locality-sensitive Hashing Ulam metric Cayley Metric Distortion Permutations Representation Theory Locality-sensitive hashing (LSH) has found widespread use as a fundamental primitive, particularly to accelerate nearest neighbor search. An LSH scheme for a similarity function S:𝒳 Γ— 𝒳 β†’ [0,1] is a distribution over hash functions on 𝒳 with the property that the probability of collision of any two elements x,y ∈ 𝒳 is exactly equal to S(x,y). However, not all similarity functions admit exact LSH schemes. The notion of LSH distortion measures how multiplicatively close a similarity function is to having an LSH scheme. In this work, we study the LSH distortion of the Ulam and Cayley similarities, which are popular similarity measures on permutations of n elements. We show that the Ulam similarity admits a sublinear LSH distortion of O(n/√{log n}); we also prove a lower bound of Ξ©(n^{0.12}) on the best LSH distortion achievable. On the other hand, we show that the LSH distortion of the Cayley similarity is Θ(n). Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Flavio Chierichetti and Mirko Giacchini and Ravi Kumar and Erasmo Tani 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.59 urn:nbn:de:0030-drops-277765 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.59 eng https://creativecommons.org/licenses/by/4.0/legalcode