65 citations · 177 across the 68 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.CC2015
Communication Complexity of Permutation-Invariant Functions
Badih Ghazi, Pritish Kamath, Madhu Sudan
Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of "permutation-invariant" functions. A partial function…
cs.CC2015
Communication with Contextual Uncertainty
Badih Ghazi, Ilan Komargodski, Pravesh Kothari +1
We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributiona…