All You Need are Random Walks: Fast and Simple Distributed Conductance Testing

Batu, Tuğkan; Trehan, Amitabh; Trehan, Chhaya

Abstract

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 random walks of O(log n) length from a certain number of random sources, at the end of which nodes can decide if the underlying network is a good conductor or far from it. Unlike previous algorithms, no aggregation is required even with a smaller number of walks. Our main technical contribution involves a tight analysis of this process for which we use spectral graph theory. We introduce and leverage the concept of sticky vertices which are vertices in a graph with low conductance such that short random walks originating from these vertices end in a region around them. The present state-of-the-art distributed CONGEST algorithm for the problem by Fichtenberger and Vasudev [MFCS 2018], runs in O(log n) rounds using three distinct phases : building a rooted spanning tree (preprocessing), running O(n 100) random walks to generate statistics (Phase 1), and then convergecasting to the root to make the decision (Phase 2). The whole of our algorithm is, however, similar to their Phase 1 running only O(m 2) = O(n 4) walks. Note that aggregation (using spanning trees) is a popular technique but spanning tree(s) are sensitive to node/edge/root failures, hence, we hope our work points to other more distributed, efficient and robust solutions for suitable problems .

Citation

Batu, T., Trehan, A., & Trehan, C. (in press). All You Need are Random Walks: Fast and Simple Distributed Conductance Testing.

• Conference Name: SIROCCO 2024: 31st International Colloquium On Structural Information and Communication Complexity
• Conference Location: Vietri sul Mare, Salerno, Italy
• Start Date: May 27, 2024
• End Date: May 29, 2024
• Acceptance Date: Jan 28, 2024
• Deposit Date: Feb 28, 2024
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743
• Public URL: https://durham-repository.worktribe.com/output/2289656
• Publisher URL: https://link.springer.com/conference/sirocco