Stochastic Distance in Property Testing
<|reference_start|>Stochastic Distance in Property Testing: We introduce a novel concept termed "stochastic distance" for property testing. Diverging from the traditional definition of distance, where a distance $t$ implies that there exist $t$ edges that can be added to ensure a graph possesses a certain property (such as $k$-edge-connectivity), our new notion implies that there is a high probability that adding $t$ random edges will endow the graph with the desired property. While formulating testers based on this new distance proves challenging in a sequential environment, it is much easier in a distributed setting. Taking $k$-edge-connectivity as a case study, we design ultra-fast testing algorithms in the CONGEST model. Our introduction of stochastic distance offers a more natural fit for the distributed setting, providing a promising avenue for future research in emerging models of computation.<|reference_end|>
@article{meir2024stochastic,
    title={Stochastic Distance in Property Testing},
    author={Uri Meir, Gregory Schwartzman, Yuichi Yoshida},
    journal={arXiv preprint arXiv:2407.14080},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.14080},
    primaryClass={cs.DC}
}