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…