On the LSH Distortion of Ulam and Cayley Similarities
Abstract
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 is a distribution over hash functions on with the property that the probability of collision of any two elements is exactly equal to . 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 elements. We show that the Ulam similarity admits a sublinear LSH distortion of ; we also prove a lower bound of on the best LSH distortion achievable. On the other hand, we show that the LSH distortion of the Cayley similarity is .
Keywords and phrases:
Locality-sensitive Hashing, Ulam metric, Cayley Metric, Distortion, Permutations, Representation TheoryCategory:
RANDOMFunding:
Flavio Chierichetti: Work done in part while at Sapienza University of Rome. Supported in part by BiCi – Bertinoro international Center for informatics, by a Google Focused Research Award and by the PRIN project 20229BCXNW (funded by the European Union – Next Generation EU, Mission 4 Component 1 CUP B53D23012910006).Copyright and License:
2012 ACM Subject Classification:
Theory of computation Data structures design and analysis ; Information systems Similarity measures ; Theory of computation Lower bounds and information complexity ; Theory of computation Nearest neighbor algorithmsAcknowledgements:
The authors wish to thank Alessandro Panconesi for providing useful ideas for the project.Editors:
Mohit Singh and Tom GurSeries and Publisher:
Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik
1 Introduction
Locality-sensitive hashing (LSH) is an important tool for processing high dimensional data [4, 5, 13, 12]. Classic examples of LSH include minHash for the Jaccard similarity [4, 5], simHash for the cosine similarity [6], and sampling hash for the Hamming similarity [12]. LSH has been extensively used for solving (approximate) nearest-neighbor search [1] and similarity search [11, 16, 20]; see https://www.mit.edu/˜andoni/LSH/ for more pointers on classical results.
LSH is a way to represent a similarity – which in the context of this paper is a bi-variate, reflexive, symmetric function – by a distribution over partitions. These partitions correspond to the pre-images of hash functions, so that two entities are considered similar by a hash function if they both hash to the same value. In other words, an LSH family induces a collision kernel of the form , for entities in the universe.
Such collision kernels have to satisfy two constraints: they have unit diagonals (capturing reflexivity) and are a convex combination of equivalence-relation matrices (capturing hashing to the same value). Hence, it turns out that many natural and useful similarity measures do not admit an LSH. An interesting line of work studies which similarities have an LSH. Charikar [6] identified a necessary condition for a similarity to admit an LSH: the corresponding distance function (which is often one minus the similarity) must be a metric and must be isometrically embeddable into .
To circumvent this, Chierichetti et al. [9] introduced the notion of LSH distortion, which answers the question: how much is a non-LSHable similarity multiplicatively close to an LSHable similarity?
Formally, given a similarity that does not admit an LSH, is there another similarity that has an LSH and satisfies:
| (1) |
We call the optimal in (1) the LSH distortion of .
In their paper, Chierichetti et al. showed tight LSH distortion bounds for several set similarities. Note that, since we are considering multiplicative approximations over similarities, and we wish to achieve them using collision kernels, the LSH distortion of a similarity can differ significantly from its metric counterpart, and known results for metric distortion do not transfer to this setting.
Our contributions
In this work, we study the LSH distortion of two natural similarities derived from popular metrics on permutations. The first is the normalized Ulam similarity, which measures the length of the longest common subsequence between two permutations. The second is the Cayley similarity, which is the normalized number of cycles in the relative permutation (its distance counterpart is number of transpositions needed to turn one permutation into another).
Our main results are the following:
-
We show that the Ulam similarity has sublinear LSH distortion. In particular, we show that it can be approximated by a similarity that has an LSH, with distortion (Theorem 5),
-
We also show a lower bound of on the LSH distortion of the Ulam similarity (Theorem 10),
-
In contrast, we show that the Cayley similarity has an lower bound on its LSH distortion (Theorem 19), matching a simple upper bound (Theorem 18).
Techniques
The proof of the upper bound for the Ulam similarity is based on computing a suitable measure of correlation between the given permutation and a random permutation. The collision probability of our scheme depends on how well the input permutations are correlated with a random one. Showing that the collision probability is upper bounded by is relatively easy. On the other hand, showing it is also lower bounded by the LCS (up to sublinear distortion) is more challenging.
For the lower bounds on the distortion, we crucially utilize the PSDness of the collision kernel (Lemma 4). The lower bound for the Ulam similarity is based on first constructing a small set of permutations on an 8-element universe that has an LSH distortion of at least 9/7, and then amplifying its cardinality to work for a universe of arbitrarily large size, by using the wreath product on permutations.
The lower bound for the Cayley similarity is based on representation theory, and uses both the fact that every bi-invariant PSD kernel on can be written as a convex combination of normalized characters, as well as Roichman’s character-ratio estimates applied to derangements. The distortion lower bound is obtained by constructing two derangements that share the high-order terms of this decomposition and hence must have close collision probabilities with the identity permutation, but have vastly different Cayley similarities (linear vs constant) to it.
Related work
For permutation metrics, the Ulam metric has been extensively studied through its connection to edit distance and longest common subsequences. Charikar and Krauthgamer [8] proved that the Ulam metric embeds into with distortion; Andoni and Krauthgamer [3] later proved that embeddings of the Ulam metric into requires a near-tight distortion of . Andoni et al. [2] bypassed the barrier by embedding Ulam distance with constant distortion into an iterated product metric. Charikar et al. [7] obtained an distortion randomized embedding of Ulam into Hamming space that also carries alignment information. Note that all these previous results are for the Ulam metric; to the best of our knowledge, the corresponding question of Ulam similarity has not been considered in the literature.
Unlike Ulam, the Cayley metric is not hard to embed into . Our work can be viewed as a hardness result for LSHability of the Cayley similarity.
Outline
We begin, in Section 2, by introducing some basic notation. In Section 3, we review the definition of LSH distortion and introduce in detail the central problems of the paper. In Section 4, we provide our upper bound on the LSH distortion for the Ulam similarity. We then give a lower bound in Section 5. In Section 6, we give a simple upper bound on the distortion of the Cayley similarity, that we complement with a matching lower bound in Section 7.
In the appendix of the full version of the paper, we also review some background on the representation theory of , which we rely on for our proofs in Section 7.
2 Notation
Permutations
For a positive integer , let . Let be the set of all permutations of . We denote by the identity permutation. For a permutation we will sometimes use the one-line notation and sometimes the cycle decomposition.111For example, for the permutation such that , , , , ; the one-line representation is and the cycle decomposition is . For a permutation we denote with the number of cycles in its cycle decomposition. Note that for any . For , we write to indicate that comes before in the one-line representation of (alternatively that . We write to indicate that either or . For we denote with the length of the longest common subsequence between the one-line representations of and . For , we denote with the number of fixed points of and with the number of cycles of length two in the cycle decomposition of . We also let .
Partitions and Compositions
Recall that, for any positive integer , a partition of is a finite sequence of non-increasing positive integers that sum to . We write to indicate that is a partition of . We denote by the partition containing s. Given a partition its transpose partition (sometimes also called the conjugate partition) is the partition defined by , where:
A composition of is an ordered partition of , i.e., an integer vector such that for every and .
Matrices
A symmetric matrix is positive semidefinite (PSD, written ) if for all , we have:
The trace operator is the function that takes in a square matrix and returns . Given two square matrices , we denote by the block matrix:
where is the all-zeros matrix.
3 Similarities, LSH, and Distortion
Definition 1 (Similarity).
Given a set , a similarity (or similarity function) on is a function , satisfying:
- (a) Reflexivity:
-
for all ,
- (b) Symmetry:
-
for all .
A similarity space is simply a pair , where is a set, and is a similarity function on .
Given a similarity space, it is natural to ask whether one can find a small representation for elements of that preserve the values of . A natural approach to obtaining this is locality-sensitive hashing, which aims to construct randomized embeddings of into discrete (-) similarity spaces that preserve in expectation. We recall the key definition here.
Definition 2 (Locality-Sensitive Hashing (LSH)).
A locality-sensitive hashing (LSH) scheme for a similarity space is a distribution over functions from into some finite set with the property that:
for all .
We say that a similarity function is LSHable if it admits an LSH scheme.
Chierichetti et al. [9] give a notion of distortion for similarity functions, quantifying the degree to which non-LSHable similarities are far from being LSHable. We recall the key definitions.
Definition 3 ([9]).
We say a distribution over functions from to some finite set -approximates the space , if:
for all . The LSH distortion (or simply distortion) of a similarity space is the smallest such that there exists a distribution that -approximates .
A simple argument shows that the distortion of a similarity space could be characterized as the smallest such that there exists an LSHable similarity function with the property that:
| (2) |
for all .
The focus of this work is the distortion of two similarity spaces in which is the symmetric group : the Ulam similarity and the Cayley similarity.
Ulam Similarity
The Ulam distance between two permutations is defined as
We define the (normalized) Ulam similarity in a natural way:
Cayley Similarity
The Cayley distance between two permutations is defined as the minimum number of (not necessarily adjacent) transpositions required to transform one permutation into the other, and it is also equivalent to (see, e.g., [10, page 118]). We define a notion of (normalized) Cayley similarity in a natural way:
Positive Semi-Definiteness
In order to prove lower bounds on the achievable distortion, we will use the following result. Let be a probability distribution over functions from a finite domain into a finite range . Fixing any ordering of the elements of , we define the matrix such that:
for .
We now show that this matrix is always PSD.
Lemma 4.
For any distribution over functions from to , where and are finite sets, the matrix is PSD. That is, for all , we have:
Proof.
Note that for any ,
where is the indicator function, and hence:
Now, for a fixed , we show that the inner sum is non-negative, which in turns completes the proof. We have:
4 Upper Bound for Ulam Similarity
In this section, we prove the following result:
Theorem 5.
The LSH distortion of is .
For two permutations and , define:
Intuitively, is the set of new record maxima according to obtained while scanning the one-line representation of starting from .
For , define:
Let be the uniform distribution over the set of functions: . Recall that for :
We will show that: .
Lemma 6.
For , , it holds that:
Proof.
Note that for , we have that if and only if . Conditioned on the choice of and , there are possible values for and only of them make the hashes of and equal. This concludes the proof.
Lemma 7.
For any and , it holds that:
Proof.
Since , the set is always non-empty, proving the first inequality.
We now show the second inequality. If there is only one element in the intersection, the result is trivially true, since for any . Otherwise, consider any distinct . Suppose without loss of generality that . By definition of , since is observed after in the one-line representation of , it must hold that . Moreover, we have , for otherwise we would have , leading to a contradiction.
Therefore, if we let , we also have , meaning that is a common subsequence of and , and therefore .
Fixed such that , define and let be a longest common subsequence. For , define the intervals:
Define also .
Lemma 8.
For any such that , it holds that:
Proof.
Consider the case , otherwise the result is trivial, since the right-hand side is always less than . For , and , suppose that:
Under this assumption, it holds that: . Indeed, we have that is the maximum (according to ) of all indices between and in the one-line representation of and therefore it will be added to when starting from (and the same argument holds for ).
By Lemma 6 and the remark above, we have:
where the last inequality follows from the remark above and the last equality uses that for a uniform at random , the element ranked highest among is chosen uniformly at random among its elements.
Lemma 9.
For any such that , it holds that:
Proof.
For , define:
For and , define . Note that, for , we have:
| (3) |
Therefore, we have:
| (4) |
For a fixed , by the Cauchy–Schwarz inequality, we have:
| (5) |
Note that each element of can be counted at most twice in and it can appear in at most two ’s, therefore:
Moreover, each can appear in at most distinct for , giving:
Combining this inequality with (5) gives:
Plugging this inequality into (4) we obtain:
where the last inequality uses that for :
We are now ready to prove the main result of this section:
Proof of Theorem 5.
It is sufficient to show that for each it holds that:
Note that if then . Therefore, consider the case where . By combining Lemma 6 and Lemma 7 we have:
| (6) |
Therefore, we only have to prove to conclude the proof. Consider first the case where . In this case we have:
Consider now the case and denote . By combining Lemma 8 and Lemma 9 we obtain:
| (7) |
By (6) we also have:
| (8) |
We split the case in two sub-cases. Suppose first that . Then, (8) gives: . Suppose instead that . Then, by (7) we have:
where we used that for .
5 Lower Bound for Ulam Similarity
In this section, we prove the following result.
Theorem 10.
Let be any integer of the form , for integer . The LSH distortion of is , where .
At a high level, we obtain a lower bound on the LSH distortion by starting with a small instance that exhibits constant distortion, and then iteratively amplifying it to handle larger values of . In each step, both the distortion bound and the permutation domain grow quadratically. Our base case has , therefore our construction produces instances for any of the form , where is a non-negative integer. The main tool enabling this amplification is the wreath product.
For any two subsets , we define the similarity matrix by for any and . For simplicity, when and are the same, we will adopt a lighter notation, and denote by the matrix . We note that the matrix has a simple block structure:
where we fixed an ordering in which the permutations in come before those in .
Definition 11 (Witness).
For , let be disjoint subsets such that and . Let be a PSD block matrix such that:
where are entry-wise non-negative symmetric matrices such that .We call the triple a witness of size and we define its value to be:
We now show that the existence of a witness implies a lower bound to the LSH distortion for Ulam similarity on .
Lemma 12.
Let be a witness of size (Definition 11). Then, the LSH distortion for Ulam similarity space is at least the value of the witness, , even when restricted only to permutations in .
Proof.
Consider any distribution over functions on which -approximates for . For every we have:
| (9) |
Note that, having fixed an ordering of the elements of that puts the elements of before the elements of , gets naturally divided into four square blocks:
By Lemma 4, and , we have . Expanding blockwise, and using and , we have:
Note that, by Equation 9, and for all . Therefore, we have:
Since , we have . Hence,
For permutations the wreath product is defined as follows. The elements of are partitioned into blocks where the th block, , contains elements . The resulting permutation is obtained by permuting the elements in each block with the inner permutation and then permuting the blocks with the outer permutation . For two sets , we define . We use the following key property of the wreath product for amplification:
Lemma 13.
For any we have:
Proof.
In the permutation , the blocks appear in the order given by , and within every block the elements appear in the order given by ; similarly for .
We first prove that . Let be any common subsequence of and . Since the alphabets are pairwise disjoint, an element from a block can only be matched with the same element from the same block . Therefore, if we track the sequence of block indices that contribute at least one matched element to , then this is a common subsequence of the outer permutations and ; thus, the number of contributing blocks is at most .
Let be any contributing block. The matched elements of in this block is a common subsequence of the ordering of inside and the ordering of inside . These two internal orderings are and , relabeled with the alphabet ; therefore, this block contributes at most matched elements. Summing over all contributing blocks, we obtain
We now show . Consider an optimal common subsequence of the outer permutations and , consisting of block indices. For each such matched block , consider an optimal common subsequence of the inner permutations and , relabeled using . Since the block indices appear in the same relative order in both and , concatenating these common subsequences over the chosen blocks yields a valid common subsequence of and of length .
We now show how to use the wreath product to amplify the size of the witness. We will make use of the Kronecker product. We recall that for two matrices and , the Kronecker product is the following block matrix:
Lemma 14.
Consider any disjoint sets with . Let and . Then, we have:
Proof.
Let and suppose that , . By Lemma 13,
Then, by considering the ordering over obtained by the ordering of when we consider first the outer permutation and then the inner permutation (and similarly for ), we have that each entry of the matrix is equivalent to the Kronecker product.
Lemma 15.
Let be a witness of size . Let , , and:
Then, is a witness of size and .
Proof.
Note that and are non-negative and symmetric. Moreover, since , we have that . Define:
Since is a principal sub-matrix of , we have that . Observe now that , and therefore since for any matrix and any matrix , . Moreover, by Lemma 14 and since , we also have . Then, is a valid witness of size . We now compute its value.
For matrices it holds that . By using this property, and by Lemma 14, we have:
Note that since , . Then:
We now provide our starting instance.
Proposition 16.
There exists a witness of size and value .
Proof.
Let and , where and :
Since is obtained from by relabeling, we have . A direct computation gives
The matrix for this instance is given by (where is the all-ones matrix). First,
Next, it is easy to calculate
Hence, .
Lemma 17.
There exists a constant such that, for any , there exists such that the LSH distortion of the Ulam similarity on is at least .
Proof.
Let and . Let be the smallest integer such that , we set . Note that .
Starting from the witness of Proposition 16 and applying Lemma 15 times we obtain a witness of size and value . By Lemma 12, this implies that the LSH distortion on is at least:
for .
Note that Lemma 17 directly implies Theorem 10. The proof is elementary.
6 Upper Bound for Cayley Similarity
In this section, we show that the LSH distortion for Cayley similarity is no more than .
Theorem 18.
The LSH distortion of is at most .
Proof.
Let be the uniform at random distribution over the functions . Clearly, for each , :
Since for all , we have:
7 Lower Bound for Cayley Similarity
In this section, we show the following result:
Theorem 19.
The LSH distortion of is .
The proof will rely on some standard results in the representation theory of . For convenience, we review these standard results in the appendix of the full version of the paper (see also, e.g., [19, 14, 17]).
We begin with the following definition:
Definition 20 (Bi-invariance).
We say that a function is bi-invariant if:
for any . We say a bi-invariant function is a bi-invariant PSD kernel if, in addition, it satisfies:
for every . We also require that for to be a PSD kernel.
Recall that a class function on is a function that is constant on each conjugacy class of . We recall the following property of bi-invariant functions. (Note that equivalent results are known in the literature, and hold for more general groups – see, e.g., [14, Chapter 4.5] – but we include a proof anyway for completeness.)
Lemma 21.
A function is bi-invariant if and only if there exists a class function such that:
for every .
Proof.
Let be a bi-invariant function. Define as:
Then we have:
for any . Moreover, is a class function, since, for any :
where the second equality follows from the bi-invariance of .
On the other hand, suppose that is a function such that for some class function , then, for any :
and:
where the second equality uses the fact that is a class function. Hence is bi-invariant.
A crucial property of the Cayley similarity is that it is bi-invariant, as we now show.
Lemma 22.
is bi-invariant.
Proof.
We have that, for any choice of and , . Since any two conjugate permutations have the same cycle type, the function is a class function, and the result follows from Lemma 21.
Definition 23 (Bi-invariant Distribution over Functions).
We will say that a distribution over functions from into some set is bi-invariant if the function is bi-invariant.
We now show that when studying the minimum achievable distortion for , any LSH family can be assumed to be bi-invariant.
Lemma 24.
Suppose there exists a distribution over functions from into a finite set that -approximates , then there exists a bi-invariant distribution that -approximates .
Proof.
We construct by pre-composing the elements of with random left and right permutations: define a function as , where is drawn from and are drawn uniformly and independently from . We first show that -approximates . For every choice of , we have:
where the first inequality uses that -approximates . Similarly:
Showing that indeed -approximates . Finally, we verify that is bi-invariant. For any and any left multiplier and right multiplier :
Because and are drawn uniformly from the group, the products and are also uniformly distributed. Thus, the expectation is identical to , completing the proof.
Note also that, by Lemma 4, is PSD and it is therefore a bi-invariant PSD kernel.
Recall that each partition is associated with a distinct irreducible representation of , we denote by its character, and by its dimension.
Lemma 25.
Any bi-invariant PSD kernel on can be written as a convex combination of normalized characters of irreducible representations of as follows:
where and .
Proof.
Let be the class function satisfying:
the existence of which is guaranteed by Lemma 21. By a result of Kondor [14, Corollary 4.5.5222We remark that Kondor’s result is stated in terms of what he refers to as “Positive Definite” kernels, which are, in reality, positive semidefinite kernels, as he himself explains earlier in the thesis.], since is PSD, we have:
| (10) |
for some choice of , where each .
For our asymptotic bounds, it is necessary to isolate the trivial representation , where and and the sign representation , where and . Thus, it is helpful to write
| (11) |
For a permutation , the fixed-point count is defined as i.e., the number of length-1 cycles. A derangement is a permutation that moves all elements, i.e., . For any , we also define the value as . We recall the following result.
Theorem 26 ([18]).
There exist absolute constants and such that for any partition , any and any permutation :
Theorem 26 allows us to prove the following.
Lemma 27.
There exist absolute constants and such that for any , any partition , and any derangement ,
where .
Proof.
Since is a derangement, ; therefore . Furthermore, from the definition of , we have:
Substituting these into the bound from Theorem 26 yields:
Lemma 28 (Theorem 1.2 (i) from [15], paraphrased).
For any derangement and any partition :
Lemma 29.
For any partition with , it holds that:
Proof.
Let . By the hook length formula (see the appendix of the full version of the paper), we have:
where the last inequality used the fact that .
Lemma 30.
Consider any sufficiently large , any derangement , and let be a bi-invariant PSD kernel. Let:
be the decomposition guaranteed by Lemma 25, then:
for some constant .
Proof.
We have:
where we first apply Hölder’s inequality on and and then we use the fact that , as well as the non-negativity of the s. We now give an upper bound for the right-hand side. Let and be the constants given by Lemma 27. Let , and let . Since , we have . We obtain an upper bound by considering five possible cases for the value of .
- Case 1:
-
. Using Lemma 27, we have:
For the rest of the proof we will assume that . This is without loss of generality, since, for any partition that does not satisfy this condition (i.e., for which ), its transpose partition does satisfy it, and the values of are the same for the two partitions.
- Case 2:
-
. Using Lemma 27 we have:
- Case 3:
- Case 4:
-
. In this case, the only partition is , corresponding to the standard representation, which has dimension . Its character is known to satisfy (See [19, Example 2.3.8]). Since is a derangement, , and the character . We then have:
- Case 5:
-
. In this case, the only two partitions are and .
By (19) in Example 32 in the appendix of the full version of the paper, we can write the character of the permutation module as the sum of irreducible characters as follows:
By equation (17) in the appendix of the full version of the paper, this equation becomes:
for all , where is the number of length-two cycles in the cycle decomposition of . And hence:
for all .
Similarly, by Equation (20) in Example 32 in the appendix of the full version of the paper, we can write the character of the permutation module as:
By Equation (18) in that same appendix, this equation becomes:
for all , which gives:
for all . Since is a derangement and , we have:
and:
By Example 21 in the appendix of the full version of the paper: and . Putting things together, we have that:
and:
This completes the proof of Lemma 30.
We can now complete the proof of Theorem 19.
Proof of Theorem 19.
Let be a large enough integer so that Lemma 30 holds. Let be a distribution that -approximates . Without loss of generality, by Lemma 24, we can assume that is a bi-invariant PSD kernel.
We let be a derangement with cycles and be a derangement with cycles and having the same sign as . We explicitly define these permutations expressing them in their cycle decomposition. If is even, we let:
and observe that . If instead is odd, we define:
and observe that and can be decomposed in transpositions. Now, if is even and or if is odd and , we define:
and note that since it can be decomposed into transpositions. If instead is even and or if is odd and , we define:
and note that since it can be decomposed into transpositions.
Observe that, since :
Since -approximates , we have:
Plugging this into (11), and letting be the constant in the statement of Lemma 30:
giving:
| (12) |
Again applying Equation 11 and Lemma 30, we have:
On the other hand:
Combining the last two equations yields:
completing the proof.
8 Conclusions and Open Questions
Our work shows that the Ulam similarity enjoys sublinear LSH distortion whereas the Cayley similarity does not. An obvious open problem is to close the glaring yet tantalizing gap between the upper bound () and the lower bound () for the Ulam similarity; our current belief is that the correct LSH distortion bound is . Improving the base case (Proposition 16) is a natural direction, though there are computational limitations to finding a larger and better base instance. While it seems possible to improve our upper bound to , going beyond this to might require an entirely new approach. Extending our results to other permutation similarities such as reversal is another interesting direction; our current lower bound techniques seem inadequate for the block reversal similarity, for which we conjecture an lower bound.
LLM Usage
The Ulam upper bound was obtained after weeks of interaction with and help from an LLM; the LLM-generated proof was hand-verified and somewhat simplified. The solver for the base case of the Ulam lower bound was written by an LLM; the instance itself was hand-verified. The high-level approach of using representation theory, in particular, Roichman’s Theorem and derangements, to obtain the Cayley lower bound was suggested by an LLM (after the initial attempts to extend Ulam lower bound proof approach to Cayley failed). All the final proofs were written and verified by the authors.
References
- [1] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. CACM, 51(1):117–122, 2008. doi:10.1145/1327452.1327494.
- [2] Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. Overcoming the l non-embeddability barrier: algorithms for product metrics. In SODA, pages 865–874, 2009. doi:10.1137/1.9781611973068.94.
- [3] Alexandr Andoni and Robert Krauthgamer. The computational hardness of estimating edit distance. SICOMP, 39(6):2398–2429, 2010. doi:10.1137/080716530.
- [4] Andrei Z Broder. On the resemblance and containment of documents. In SEQUENCES, pages 21–29, 1997. doi:10.1109/SEQUEN.1997.666900.
- [5] Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. Min-wise independent permutations. JCSS, 60(3):630–659, 2000. doi:10.1006/JCSS.1999.1690.
- [6] Moses Charikar. Similarity estimation techniques from rounding algorithms. In STOC, pages 380–388, 2002. doi:10.1145/509907.509965.
- [7] Moses Charikar, Ofir Geri, Michael P. Kim, and William Kuszmaul. On estimating edit distance: Alignment, dimension reduction, and embeddings. In ICALP, pages 34:1–34:14, 2018. doi:10.4230/LIPIcs.ICALP.2018.34.
- [8] Moses Charikar and Robert Krauthgamer. Embedding the Ulam metric into l. Theory Comput., 2(11):207–224, 2006. doi:10.4086/TOC.2006.V002A011.
- [9] Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, and Erisa Terolli. On the distortion of locality sensitive hashing. SICOMP, 48(2):350–372, 2019. doi:10.1137/17M1127752.
- [10] Persi Diaconis. Group Representations in Probability and Statistics. Inst. Math. Stat., 1988.
- [11] Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. In VLDB, pages 518–529, 1999. URL: http://www.vldb.org/conf/1999/P49.pdf.
- [12] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In STOC, pages 604–613, 1998. doi:10.1145/276698.276876.
- [13] Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, and Santosh S. Vempala. Locality-preserving hashing in multidimensional spaces. In STOC, pages 618–625, 1997. doi:10.1145/258533.258656.
- [14] Imre Risi Kondor. Group Theoretical Methods in Machine Learning. Columbia U., 2008.
- [15] Michael Larsen and Aner Shalev. Characters of symmetric groups: sharp bounds and applications. Invent. Math., 174(3):645–687, 2008.
- [16] Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. Multi-probe LSH: efficient indexing for high-dimensional similarity search. In VLDB, pages 950–961, 2007. URL: http://www.vldb.org/conf/2007/papers/research/p950-lv.pdf.
- [17] Paul Renteln. A combinatorial proof of a symmetric group character involution. The American Mathematical Monthly, 130(9):855–858, 2023. doi:10.1080/00029890.2023.2242042.
- [18] Yuval Roichman. Upper bound on the characters of the symmetric groups. Invent. Math., 125:451–485, 1996.
- [19] Bruce Sagan. The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions. Springer Science & Business Media, 2001.
- [20] Venu Satuluri and Srinivasan Parthasarathy. Bayesian locality sensitive hashing for fast similarity search. Proc. VLDB Endow., 5(5):430–441, 2012. doi:10.14778/2140436.2140440.
