Testable Properties in General Graphs and Random Order Streaming
Artur Czumaj, Hendrik Fichtenberger, Pan Peng, Christian Sohler · Warwick Research Archive Portal (University of Warwick) · 2019
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.