Fichtenberger, Hendrik ;
Vasudev, Yadu
A TwoSided Error Distributed Property Tester For Conductance
Abstract
We study property testing in the distributed model and extend its setting from testing with onesided error to testing with twosided error. In particular, we develop a twosided 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 epsilonfar 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 twosided error might seem to be much stronger than in the sequential query model, we can show that this is not the case.
BibTeX  Entry
@InProceedings{fichtenberger_et_al:LIPIcs:2018:9601,
author = {Hendrik Fichtenberger and Yadu Vasudev},
title = {{A TwoSided Error Distributed Property Tester For Conductance}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {19:119:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9601},
URN = {urn:nbn:de:0030drops96019},
doi = {10.4230/LIPIcs.MFCS.2018.19},
annote = {Keywords: property testing, distributed algorithms, conductance}
}
2018
Keywords: 

property testing, distributed algorithms, conductance 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

2018 