Dominance Product and High-Dimensional Closest Pair under L_infty
From MaRDI portal
Publication:5136258
DOI10.4230/LIPIcs.ISAAC.2017.39zbMath1457.68291arXiv1605.08107OpenAlexW2963852036MaRDI QIDQ5136258
Publication date: 25 November 2020
Full work available at URL: https://arxiv.org/abs/1605.08107
Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)
Related Items (4)
Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication. ⋮ Hamming Distance Completeness ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic ⋮ On the Complexity of Closest Pair via Polar-Pair of Point-Sets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multidimensional divide-and-conquer
- The complexity of selection and ranking in X+Y and matrices with sorted columns
- Computing dominances in \(E^ n\)
- How good is the information theory bound in sorting?
- A note on Rabin's nearest-neighbor algorithm
- Fast rectangular matrix multiplication and applications
- Geometric applications of a randomized optimization technique
- Powers of tensors and fast matrix multiplication
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
- Multiplying matrices faster than coppersmith-winograd
- Automata, Languages and Programming
This page was built for publication: Dominance Product and High-Dimensional Closest Pair under L_infty