تقرير
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 |
الوصف غير متاح. |