Skip to main content

Research Repository

Advanced Search

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

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

Authors

Tuğkan Batu

Chhaya Trehan



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

This file is under embargo due to copyright reasons.



You might also like



Downloadable Citations