Distributed Lov\'asz Local Lemma under Bandwidth Limitations
<|reference_start|>Distributed Lov\'asz Local Lemma under Bandwidth Limitations: The constructive Lov\'{a}sz Local Lemma has become a central tool for designing efficient distributed algorithms. While it has been extensively studied in the classic LOCAL model that uses unlimited bandwidth, much less is known in the bandwidth-restricted CONGEST model.   In this paper, we present bandwidth- and time-efficient algorithms for various subclasses of LLL problems, including a large class of subgraph sampling problems that are naturally formulated as LLLs. Lastly, we use our LLLs to design efficient CONGEST algorithms for coloring sparse and triangle-free graphs with few colors. These coloring algorithms are exponentially faster than previous LOCAL model algorithms.<|reference_end|>
@article{halldórsson2024distributed,
    title={Distributed Lov\'{a}sz Local Lemma under Bandwidth Limitations},
    author={Magn'us M. Halld'orsson, Yannic Maus, Saku Peltonen},
    journal={arXiv preprint arXiv:2405.07353},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.07353},
    primaryClass={cs.DS cs.DC}
}