All You Need are Random Walks: Fast and Simple Distributed Conductance Testing
(2024)
Presentation / Conference Contribution
Batu, T., Trehan, A., & Trehan, C. (2024, May). All You Need are Random Walks: Fast and Simple Distributed Conductance Testing. Presented at SIROCCO 2024: 31st International Colloquium On Structural Information and Communication Complexity, Vietri sul Mare, Salerno, Italy
We propose a simple and time-optimal algorithm for property testing a graph for its conductance in the CONGEST model. Our algorithm takes only O(log n) rounds of communication (which is known to be optimal), and consists of simply running multiple ra... Read More about All You Need are Random Walks: Fast and Simple Distributed Conductance Testing.