Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication

Christian Konrad, Peter Robinson, Viktor Zamaraev

We give lower bounds on the communication complexity of graph problems in the multi-party blackboard model. In this model, the edges of an $n$-vertex input graph are partitioned am…