Cell-probe lower bounds for the partial match problem

DOI10.1145/780542.780639zbMath1192.68215OpenAlexW2016185430MaRDI QIDQ5901093

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

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780639

Mathematics Subject Classification ID

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

Related Items (2)

A lower bound for the smallest uniquely Hamiltonian planar graph with minimum degree three ⋮ An Improved Algorithm Finding Nearest Neighbor Using Kd-trees

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