Dominance Product and High-Dimensional Closest Pair under L_infty

DOI10.4230/LIPIcs.ISAAC.2017.39zbMath1457.68291arXiv1605.08107OpenAlexW2963852036MaRDI QIDQ5136258

Omer Gold, Micha Sharir

Publication date: 25 November 2020

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

zbMATH Keywords

closest pairrectangular matrix multiplication\(L_\infty\) proximitydominance product

Mathematics Subject Classification ID

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