Lower bounds for union-split-find related problems on random access machines
From MaRDI portal
Publication:2817656
DOI10.1145/195058.195415zbMath1345.68118OpenAlexW2050108834MaRDI QIDQ2817656
Publication date: 1 September 2016
Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/60938/7/WRAP_cs-rr-258.pdf
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)
Related Items (22)
Dynamic nested brackets ⋮ ANN for time series under the Fréchet distance ⋮ A strong lower bound for approximate nearest neighbor searching ⋮ Predecessor queries in dynamic integer sets ⋮ Sorting and searching revisted ⋮ Lower bounds for dynamic transitive closure, planar point location, and parentheses matching ⋮ Neighbours on a grid ⋮ Dynamic algorithms for the Dyck languages ⋮ On the difficulty of range searching ⋮ Fully Dynamic Transitive Closure in plane dags with one source and one sink ⋮ Optimal collapsing protocol for multiparty pointer jumping ⋮ On the cell probe complexity of polynomial evaluation ⋮ Lower bounds for predecessor searching in the cell probe model ⋮ On the difficulty of range searching. ⋮ Tighter lower bounds for nearest neighbor search and related problems in the cell probe model ⋮ Cell-probe lower bounds for the partial match problem ⋮ Unnamed Item ⋮ On data structures and asymmetric communication complexity ⋮ Improved fast integer sorting in linear space ⋮ Lower bounds for dynamic algebraic problems ⋮ Protocols for asymmetric communication channels ⋮ Optimal bounds for the predecessor problem and related problems
This page was built for publication: Lower bounds for union-split-find related problems on random access machines
