Czumaj, Artur, Fichtenberger, Hendrik, Peng, Pan and Sohler, Christian (2020) Testable properties in general graphs and random order streaming. In: 24th International Conference on Randomization and Computation (RANDOM 2020), Virtual, USA, 17-19 Aug 2020 (In Press)

Preview	PDF main.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (586Kb) | Preview
Preview	PDF WRAP-Testable-properties-general-graphs-random-streaming-Czumaj-2020.pdf - Unspecified Version - Requires a PDF viewer. Download (586Kb) | Preview

Request Changes to record.

Abstract

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.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics T Technology > TK Electrical engineering. Electronics Nuclear engineering
Divisions:	Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH):	Computer algorithms, Graph algorithms , Streaming technology (Telecommunications)
Publisher:	LIPICS (Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany)
Official Date:	8 June 2020
Dates:	Date Event 8 June 2020 Accepted
Date of first compliant deposit:	22 July 2020
Status:	Peer Reviewed
Publication Status:	In Press
Access rights to Published version:	Open Access
Copyright Holders:	licensed under Creative Commons License CC-BY
RIOXX Funder/Project Grant:	Project/Grant ID RIOXX Funder Name Funder ID EP/N011163/1 [EPSRC] Engineering and Physical Sciences Research Council http://dx.doi.org/10.13039/501100000266 Faculty Award IBM Center for the Business of Government http://dx.doi.org/10.13039/100014026 307696 [ERC] Horizon 2020 Framework Programme http://dx.doi.org/10.13039/100010661
Conference Paper Type:	Paper
Title of Event:	24th International Conference on Randomization and Computation (RANDOM 2020)
Type of Event:	Conference
Location of Event:	Virtual, USA
Date(s) of Event:	17-19 Aug 2020
Open Access Version:	ArXiv

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads