Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST
Yuval Efron, Ofer Grossman, Seri Khoury · 2020
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 results for various fundamental problems such as distance computations, minimum spanning tree, minimum vertex cover, and more.