تقرير
Stochastic Distance in Property Testing
| العنوان: | Stochastic Distance in Property Testing |
|---|---|
| المؤلفون: | Meir, Uri, Schwartzman, Gregory, Yoshida, Yuichi |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Distributed, Parallel, and Cluster Computing |
| الوصف: | 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. Comment: To be published in RANDOM 2024 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2407.14080 |
| رقم الأكسشن: | edsarx.2407.14080 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |