Cell-probe lower bounds for the partial match problem.

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

Browse the full STOC paper archive.