Necklaces, convolutions, and \(X+Y\)

DOI10.1007/s00453-012-9734-3zbMath1360.68498arXiv1212.4771OpenAlexW2174643652MaRDI QIDQ517795

Ferran Hurtado, Jeff Erickson, Erik D. Demaine, John Iacono, Mihai Pǎtraşcu, Stefan Langerman, David Bremner, Perouz Taslakian, Timothy M. Chan

Publication date: 27 March 2017

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

convolutionall pairs shortest pathscyclic swap distancenecklace alignmentsorting \(X+Y\)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Combinatorial optimization (90C27) Algorithms on strings (68W32) Mathematics and music (00A65)

Related Items (16)

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ Unnamed Item ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ Derivative-free mixed binary necklace optimization for cyclic-symmetry optimal design problems ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ A polyhedral perspective on tropical convolutions ⋮ Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model ⋮ Efficient indexes for jumbled pattern matching with constant-sized alphabet ⋮ Unnamed Item ⋮ Extreme witnesses and their applications ⋮ Smallest \(k\)-enclosing rectangle revisited ⋮ Smallest k-enclosing rectangle revisited ⋮ On Integer Programming and Convolution. ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A pseudo-algorithmic separation of lines from pseudo-lines
• Simple deterministic wildcard matching
• Juggling with pattern matching
• Gauss and the history of the fast Fourier transform
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• How good is the information theory bound in sorting?
• Finding the median
• Fast algorithms for the maximum convolution problem
• Time bounds for selection
• Approximate string matching for music analysis
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• Subquadratic algorithms for 3SUM
• Inf-convolution, sous-additivite, convexite des fonctions numériques
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• Mathematical Programming and the Maximum Transform
• Self-normalised Distance with Don’t Cares
• Verifying candidate matches in sparse and wildcard matching
• New Bounds on the Complexity of the Shortest Path Problem
• NECKLACE SWAP PROBLEM FOR RHYTHMIC SIMILARITY MEASURES
• An Algorithm for the Machine Calculation of Complex Fourier Series
• The Geometry of Musical Rhythm
• Convex Analysis
• Combinatorial Pattern Matching

This page was built for publication: Necklaces, convolutions, and \(X+Y\)