Relating two property testing models for bounded degree directed graphs
- Submitting institution
-
The University of Sheffield
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 2595
- Type
- E - Conference contribution
- DOI
-
10.1145/2897518.2897575
- Title of conference / published proceedings
- STOC '16: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
- First page
- 1033
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- June
- Year of publication
- 2016
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
A - Algorithms
- Citation count
- 5
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper provides a generic transformation between two fundamental property testing models for bounded degree directed graphs, leading to new property testing algorithms for many properties and subsumes and unifies several existing results. The paper was invited to workshops in Moscow, Rutgers University and Baltimore and the result was included in the book "Introduction to Property Testing" by Knuth Prize recipient Prof Oded Goldreich. The results of the paper have been exploited by researchers at Leeds University to study property testing for databases (doi.org/10.4230/LIPIcs.STACS.2018.6). The introduced techniques have been used to establish connections between property testing and streaming algorithms (https://drops.dagstuhl.de/opus/volltexte/2017/7478/pdf/LIPIcs-ICALP-2017-131.pdf).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -