23 citations · 97 across the 22 of their papers we have counts for
Showing 2010Show all
2 papers · 1 filter
cs.CC2010★ 3 cited
A strong direct product theorem for two-way public coin communication complexity
Rahul Jain
We show a direct product result for two-way public coin communication complexity of all relations in terms of a new complexity measure that we define. Our new measure is a generali…
cs.CC2010★ 2 cited
Strong direct product conjecture holds for all relations in public coin randomized one-way communication complexity
Rahul Jain
Let f subset of X x Y x Z be a relation. Let the public coin one-way communication complexity of f, with worst case error 1/3, be denoted R^{1,pub}_{1/3}(f). We show that if for co…