2026-07-23T20:43:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9601 2024-03-06T10:44:30Z ddc:004 open_access

A Two-Sided Error Distributed Property Tester For Conductance Fichtenberger, Hendrik Vasudev, Yadu property testing distributed algorithms conductance We study property testing in the distributed model and extend its setting from testing with one-sided error to testing with two-sided error. In particular, we develop a two-sided error property tester for general graphs with round complexity O(log(n) / (epsilon Phi^2)) in the CONGEST model, which accepts graphs with conductance Phi and rejects graphs that are epsilon-far from having conductance at least Phi^2 / 1000 with constant probability. Our main insight is that one can start poly(n) random walks from a few random vertices without violating the congestion and unite the results to obtain a consistent answer from all vertices. For connected graphs, this is even possible when the number of vertices is unknown. We also obtain a matching Omega(log n) lower bound for the LOCAL and CONGEST models by an indistinguishability argument. Although the power of vertex labels that arises from two-sided error might seem to be much stronger than in the sequential query model, we can show that this is not the case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hendrik Fichtenberger and Yadu Vasudev 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.19 urn:nbn:de:0030-drops-96019 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.19 eng https://creativecommons.org/licenses/by/3.0/legalcode