Cell-probe lower bounds for the partial match problem

DOI10.1016/J.JCSS.2004.04.006MaRDI QIDQ5917577zbMATH OpenOpenAlexFDO

Authors T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani

Publication date 18 November 2004

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2004.04.006

zbMATH Keywords

Asymmetric communication complexityCell-probe modelNearest neighbor problemPartial match problem

Mathematics Subject Classification ID

Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Cell-probe lower bounds for the partial match problem
• Cell-probe lower bounds for succinct partial sums
• Tighter lower bounds for nearest neighbor search and related problems in the cell probe model
• Lower bounds for predecessor searching in the cell probe model
• Cell probe lower bounds for succinct data structures
• Tighter bounds for nearest neighbor search and related problems in the cell probe model
• Unifying the landscape of cell-probe lower bounds
• An optimal randomized cell probe lower bound for approximate nearest neighbor searching
• A cell probe lower bound for dynamic nearest-neighbour searching
• Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity

Cites work

• A lower bound for finding predecessors in Yao's cell probe model
• A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
• An optimal randomized cell probe lower bound for approximate nearest neighbor searching
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Hardness vs randomness
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• scientific article; zbMATH DE number 1559575 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 2086643 (Why is no real title available?)
• Lower bounds for high dimensional nearest neighbor search and related problems
• Lower bounds for union-split-find related problems on random access machines
• On approximate nearest neighbors under \(l_\infty\) norm
• On data structures and asymmetric communication complexity
• Partial-Match Retrieval Algorithms
• Point location in arrangements of hyperplanes
• Should Tables Be Sorted?
• Tighter bounds for nearest neighbor search and related problems in the cell probe model
• Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems

Cited in

(6)

• Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity
• Higher lower bounds for near-neighbor and further rich problems
• On the cell probe complexity of membership and perfect hashing
• Cell-probe lower bounds for the partial match problem
• Pattern masking for dictionary matching: theory and practice
• Tighter lower bounds for nearest neighbor search and related problems in the cell probe model

This page was built for publication: Cell-probe lower bounds for the partial match problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5917577)