4 citations · 10 across the 4 of their papers we have counts for
Showing cs.DCShow all
2 papers · 1 filter
cs.DC2020
Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST
Yuval Efron, Ofer Grossman, Seri Khoury
By far the most fruitful technique for showing lower bounds for the CONGEST model is reductions to two-party communication complexity. This technique has yielded nearly tight resul…
cs.DC2019
Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators
Lijie Chen, Ofer Grossman
We develop techniques to prove lower bounds for the BCAST(log n) Broadcast Congested Clique model (a distributed message passing model where in each round, each processor can broad…