23 citations · 145 across the 28 of their papers we have counts for
Showing 2003Show all
2 papers · 1 filter
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…
quant-ph2003★ 9 cited
A lower bound for bounded round quantum communication complexity of set disjointness
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
We consider the class of functions whose value depends only on the intersection of the input X_1,X_2, ..., X_t; that is, for each F in this class there is an f_F: 2^{[n]} \to {0,1}…