On closest pair in Euclidean metric: monochromatic is as hard as bichromatic

DOI10.1007/S00493-019-4113-1zbMath1474.68424arXiv1812.00901OpenAlexW3022115507WikidataQ114229222 ScholiaQ114229222MaRDI QIDQ2221003

Pasin Manurangsi, C. S. Karthik

Publication date: 25 January 2021

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1812.00901

zbMATH Keywords

closest pairmonochromaticbichromatic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Unnamed Item ⋮ Removing additive structure in 3SUM-based reductions ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multidimensional divide-and-conquer
• On the contact dimensions of graphs
• Algebraic function fields and codes
• Dispersed points and geometric embedding of complete bipartite graphs
• On the asymptotic behaviour of some towers of function fields over finite fields
• Which problems have strongly exponential complexity?
• 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
• A new algorithm for optimal 2-constraint satisfaction and its implications
• 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
• On the Complexity of Closest Pair via Polar-Pair of Point-Sets
• Extensions of Lipschitz mappings into a Hilbert space
• Lower Bounds on Locality Sensitive Hashing
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• Approximating Matrix Multiplication for Pattern Recognition Tasks
• The Parameterized Complexity of the k -Biclique Problem
• Hardness of approximating the minimum distance of a linear code
• From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Hardness of approximate nearest neighbor search
• On the parameterized complexity of approximating dominating set
• Automata, Languages and Programming
• Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters
• Linear codes with exponentially many light vectors

This page was built for publication: On closest pair in Euclidean metric: monochromatic is as hard as bichromatic