Optimal bounds for the predecessor problem and related problems
type: Item
instance of: scholarly article
title: Optimal bounds for the predecessor problem and related problems
zbMATH Open document ID: 1020.68027
author: Paul Beame
author: Faith E. Fich
published in: Journal of Computer and System Sciences
publication date: 2003-05-04T00:00:00Z
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 1903462
zbMATH Keywords: communication game model
Wikidata QID: Q55889025
MaRDI profile type: Publication
OpenAlex ID: W1986633843
cites work: Hash functions for priority queues
cites work: A lower bound for finding predecessors in Yao's cell probe model
cites work: Optimal static range reporting in one dimension
cites work: Efficient regular data structures and algorithms for dilation, location, and proximity problems
cites work: Q4252751
cites work: Fusion trees can be implemented with \(AC^0\) instructions only
cites work: Tight(er) worst-case bounds on dynamic searching and priority queues
cites work: Predecessor queries in dynamic integer sets
cites work: Trans-dichotomous algorithms without multiplication — some upper and lower bounds
cites work: Universal classes of hash functions
cites work: Toward optimal \(\epsilon\)-approximate nearest neighbor algorithms
cites work: A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
cites work: Q4938782
cites work: Q4515159
cites work: Q3826580
cites work: Polynomial hash functions are reliable
cites work: A Reliable Randomized Algorithm for the Closest-Pair Problem
cites work: Dynamic Perfect Hashing: Upper and Lower Bounds
cites work: Q4038677
cites work: Tables should be sorted (on random access machines)
cites work: Storing a Sparse Table with 0 (1) Worst Case Access Time
cites work: Surpassing the information theoretic bound with fusion trees
cites work: STACS 98. 15th annual symposium on theoretical aspects of computer science. Paris, France, February 25--27, 1998. Proceedings
cites work: Q4837112
cites work: Monotone Circuits for Connectivity Require Super-Logarithmic Depth
cites work: Dynamic fractional cascading
cites work: A Lower Bound on the Complexity of the Union-Split-Find Problem
cites work: Q4281568
cites work: Lower bounds for union-split-find related problems on random access machines
cites work: Q4250224
cites work: On data structures and asymmetric communication complexity
cites work: Q4952655
cites work: Understanding the complexity of interpolation search
cites work: Priority queues: Small, monotone and trans-dichotomous
cites work: Q4250223
cites work: Preserving order in a forest in less than logarithmic time and linear space
cites work: Design and implementation of an efficient priority queue
cites work: Log-logarithmic worst-case range queries are possible in space theta(N)
cites work: Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time
cites work: Should Tables Be Sorted?
DBLP publication ID: journals/jcss/BeameF02
DOI: 10.1006/JCSS.2002.1822
description: scientific article; zbMATH DE number 1903462