23 citations · 36 across the 5 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
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…
cs.CC2003★ 23 cited
A direct sum theorem in communication complexity via message compression
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
We prove lower bounds for the direct sum problem for two-party bounded error randomised multiple-round communication protocols. Our proofs use the notion of information cost of a p…