3 citations · 3 across the 1 of their papers we have counts for
3 papers
cs.CC2003★ 3 cited
Lower bounds for predecessor searching in the cell probe model
Pranab Sen, S. Venkatesh
We consider a fundamental problem in data structures, static predecessor searching: Given a subset S of size n from the universe [m], store S so that queries of the form "What is t…
quant-ph2001
Lower bounds in the quantum cell probe model
Pranab Sen, S. Venkatesh
We introduce a new model for studying quantum data structure problems -- the "quantum cell probe model". We prove a lower bound for the static predecessor problem in the address-on…
quant-ph2000
The Quantum Complexity of Set Membership
Jaikumar Radhakrishnan, Pranab Sen, S. Venkatesh
We study the quantum complexity of the static set membership problem: given a subset S (|S| \leq n) of a universe of size m (m \gg n), store it as a table of bits so that queries o…