The Library
Testable properties in general graphs and random order streaming
Tools
Tools
Tools
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. Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), 179 pp. 1-20. ISBN 9783959771641. ISSN 1868-8969. doi:10.4230/LIPIcs.APPROX/RANDOM.2020.16
|
PDF
main.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (586Kb) | Preview |
|
|
PDF
WRAP-Testable-properties-general-graphs-random-streaming-Czumaj-2020.pdf - Unspecified Version - Requires a PDF viewer. Download (586Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020....
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) | ||||||||||||
| Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||||||||
| Journal or Publication Title: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) | ||||||||||||
| Publisher: | LIPICS (Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany) | ||||||||||||
| ISBN: | 9783959771641 | ||||||||||||
| ISSN: | 1868-8969 | ||||||||||||
| Official Date: | 11 August 2020 | ||||||||||||
| Dates: |
|
||||||||||||
| Volume: | 179 | ||||||||||||
| Page Range: | pp. 1-20 | ||||||||||||
| Article Number: | 16 | ||||||||||||
| DOI: | 10.4230/LIPIcs.APPROX/RANDOM.2020.16 | ||||||||||||
| Status: | Peer Reviewed | ||||||||||||
| Publication Status: | Published | ||||||||||||
| Access rights to Published version: | Open Access | ||||||||||||
| Copyright Holders: | licensed under Creative Commons License CC-BY | ||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||
| 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: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
