文章基本信息

标题：Testable Properties in General Graphs and Random Order Streaming
本地全文：下载
作者：Artur Czumaj ; Hendrik Fichtenberger ; Pan Peng 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：176
页码：16:1-16:20
DOI：10.4230/LIPIcs.APPROX/RANDOM.2020.16
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider the fundamental question of understanding the relative power of two important computational models: property testing and data streaming. We present a novel framework closely linking these areas in the setting of general graphs in the context of constant-query complexity testing and constant-space streaming. Our main result is a generic transformation of a one-sided error property tester in the random-neighbor model with constant query complexity into a one-sided error property tester in the streaming model with constant space complexity. Previously such a generic transformation was only known for bounded-degree graphs.
关键词：Graph property testing; sublinear algorithms; graph streaming algorithms