Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
PDF
main.pdf - Published Version - Requires a PDF viewer.
Available under License Creative Commons Attribution 4.0.

Download (586Kb) | Preview
[img]
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....

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)
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:
DateEvent
11 August 2020Published
8 June 2020Accepted
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:
Project/Grant IDRIOXX Funder NameFunder ID
EP/N011163/1[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
Faculty AwardIBM Center for the Business of Governmenthttp://dx.doi.org/10.13039/100014026
307696[ERC] Horizon 2020 Framework Programmehttp://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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us