4 papers
Multi-Vector Embeddings are Provably More Expressive than Single Vector Embeddings
Rajesh Jayaram
Multi-vector (MV) embeddings have become a powerful paradigm in neural information retrieval (IR), achieving high retrieval accuracy by representing data with multiple vectors and…
Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram +1
We give a reduction from -approximate Earth Mover's Distance (EMD) to -approximate Closest Pair (CP). As a consequence, we improve the fastest kno…
Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
Jie Gao, Rajesh Jayaram, Benedikt Kolbe +4
Randomized dimensionality reduction is a widely-used algorithmic technique for speeding up large-scale Euclidean optimization problems. In this paper, we study dimension reduction…
Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins +2
Metric embeddings are a widely used method in algorithm design, where generally a ``complex'' metric is embedded into a simpler, lower-dimensional one. Historically, the theoretica…