182 citations · 670 across the 41 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.CC2013★ 2 cited
Communication Lower Bounds via Critical Block Sensitivity
Mika Göös, Toniann Pitassi
We use critical block sensitivity, a new complexity measure introduced by Huynh and Nordström (STOC 2012), to study the communication complexity of search problems. To begin, we gi…
cs.DS2013★ 4 cited
Tight Bounds for Set Disjointness in the Message Passing Model
Mark Braverman, Faith Ellen, Rotem Oshman +2
In a multiparty message-passing model of communication, there are players. Each player has a private input, and they communicate by sending messages to one another over private…