On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
From MaRDI portal
Publication:5090390
DOI10.4230/LIPIcs.ITCS.2019.17OpenAlexW2903060623MaRDI QIDQ5090390
S. Karthik C., Pasin Manurangsi
Publication date: 18 July 2022
Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2018/10110/pdf/LIPIcs-ITCS-2019-17.pdf/
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multidimensional divide-and-conquer
- Fundamentals of parameterized complexity
- On the contact dimensions of graphs
- Euclidean minimum spanning trees and bichromatic closest pairs
- Embeddings of graphs in Euclidean spaces
- A simple randomized sieve algorithm for the closest-pair problem
- Lattices with exponentially large kissing numbers
- Monotone maps, sphericity and bounded second eigenvalue
- Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem
- Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
- A Deterministic Reduction for the Gap Minimum Distance Problem
- Polynomial Codes Over Certain Finite Fields
- Extensions of Lipschitz mappings into a Hilbert space
- Powers of tensors and fast matrix multiplication
- Lower Bounds on Locality Sensitive Hashing
- Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
- Approximating Matrix Multiplication for Pattern Recognition Tasks
- Hardness of approximating the minimum distance of a linear code
- Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
- On the Complexity of Closest Pair via Polar-Pair of Point-Sets
- Dominance Product and High-Dimensional Closest Pair under L_infty
- The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
- Hardness of approximate nearest neighbor search
- On the parameterized complexity of approximating dominating set
- An Equivalence Class for Orthogonal Vectors
- The Parameterized Complexity of k-B<scp>iclique</scp>
- Automata, Languages and Programming
- Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters
- Linear codes with exponentially many light vectors
