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

Relating two property testing models for bounded degree directed graphs

Tools
- Tools
+ Tools

Czumaj, Artur, Peng, Pan and Sohler, Christian (2016) Relating two property testing models for bounded degree directed graphs. In: 48th Annual ACM Symposium on Theory of Computing (STOC 2016), Cambridge, MA, 19-21 Jun 2016. Published in: STOC 2016 Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing pp. 1033-1045. ISBN 9781450341325. doi:10.1145/2897518.2897575

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

Download (769Kb)
[img] PDF
WRAP_0583063-cs-090516-directed-v6.pdf - Accepted Version
Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer.

Download (410Kb)
Official URL: http://dx.doi.org/10.1145/2897518.2897575

Request Changes to record.

Abstract

We study property testing algorithms in directed graphs (digraphs) with maximum indegree and maximum outdegree upper bounded by d. For directed graphs with bounded degree, there are two different models in property testing introduced by Bender and Ron (2002). In the bidirectional model, one can access both incoming and outgoing edges while in the unidirectional model one can only access outgoing edges. In our paper we provide a new relation between the two models: we prove that if a property can be tested with constant query complexity in the bidirectional model, then it can be tested with sublinear query complexity in the unidirectional model. A corollary of this result is that in the unidirectional model (the model allowing only queries to the outgoing neighbors), every property in hyperfinite digraphs is testable with sublinear query complexity.

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Directed graphs
Journal or Publication Title: STOC 2016 Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
Publisher: ACM
ISBN: 9781450341325
Official Date: 18 March 2016
Dates:
DateEvent
18 March 2016Accepted
Page Range: pp. 1033-1045
DOI: 10.1145/2897518.2897575
Status: Peer Reviewed
Publication Status: Published
Funder: University of Warwick. Centre for Discrete Mathematics and Its Applications, Engineering and Physical Sciences Research Council (EPSRC), European Research Council (ERC)
Grant number: EP/J021814/1 (EPSRC), Grant No. 307696 (ERC)
Conference Paper Type: Paper
Title of Event: 48th Annual ACM Symposium on Theory of Computing (STOC 2016)
Type of Event: Conference
Location of Event: Cambridge, MA
Date(s) of Event: 19-21 Jun 2016
Related URLs:
  • Publisher
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

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