{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreif5bohay6immtadbx2a7oqr4y5luc5sw2ybawf5sqmpzhw4cpofcy",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mlzlfc6e2tu2"
  },
  "path": "/report/2026/079",
  "publishedAt": "2026-05-17T03:12:14.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "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:\\mathcal{X} \\times \\mathcal{X} \\to [0,1]$ is a distribution over hash functions on $\\mathcal{X}$ with the property that the probability of collision of any two elements $x,y\\in \\mathcal{X}$ 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 / \\sqrt{\\log n})$; we also prove a lower bound of $\\Omega(n^{0.12})$ on the best LSH distortion achievable. On the other hand, we show that the LSH distortion of the Cayley similarity is $\\Theta(n)$.",
  "title": "TR26-079 |  On the LSH Distortion of Ulam and Cayley Similarities | \n\n\tFlavio Chierichetti, \n\n\tMirko Giacchini, \n\n\tRavi Kumar, \n\n\tErasmo Tani"
}