47 citations · 138 across the 17 of their papers we have counts for
Showing 2013Show all
3 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.DC2013★ 9 cited
Linear-in- Lower Bounds in the LOCAL Model
Mika Göös, Juho Hirvonen, Jukka Suomela
By prior work, there is a distributed algorithm that finds a maximal fractional matching (maximal edge packing) in rounds, where is the maximum degree of the graph. We s…
cs.DC2013★ 39 cited
What can be decided locally without identifiers?
Pierre Fraigniaud, Mika Göös, Amos Korman +1
Do unique node identifiers help in deciding whether a network has a prescribed property ? We study this question in the context of distributed local decision, where the obje…