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

An adaptivity hierarchy theorem for property testing

Tools
- Tools
+ Tools

Canonne, Clément L. and Gur, Tom (2018) An adaptivity hierarchy theorem for property testing. computational complexity, 27 (4). pp. 671-716. doi:10.1007/s00037-018-0168-4 ISSN 1016-3328.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Official URL: http://dx.doi.org/10.1007/s00037-018-0168-4

Request Changes to record.

Abstract

Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of adaptive testing algorithms, wherein each query may be determined by the answers received to prior queries, and their non-adaptive counterparts, in which all queries are independent of answers obtained from previous queries.

In this work, we investigate the role of adaptivity in property testing at a finer level. We first quantify the degree of adaptivity of a testing algorithm by considering the number of “rounds of adaptivity” it uses. More accurately, we say that a tester is k-(round) adaptive if it makes queries in k+1 rounds, where the queries in the i ’th round may depend on the answers obtained in the previous i−1 rounds. Then, we ask the following question:
Does the power of testing algorithms smoothly grow with the number of rounds of adaptivity?

We provide a positive answer to the foregoing question by proving an adaptivity hierarchy theorem for property testing. Specifically, our main result shows that for every n∈N and 0≤k≤n0.33 there exists a property Pn,k of functions for which (1) there exists a k -adaptive tester for Pn,k with query complexity O~(k) , yet (2) any (k−1) -adaptive tester for Pn,k must make Ω~(n/k2) queries. In addition, we show that such a qualitative adaptivity hierarchy can be witnessed for testing natural properties of graphs.

Item Type: Journal Article
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Journal or Publication Title: computational complexity
Publisher: Springer
ISSN: 1016-3328
Official Date: December 2018
Dates:
DateEvent
December 2018Published
24 May 2018Available
10 January 2018Accepted
Volume: 27
Number: 4
Page Range: pp. 671-716
DOI: 10.1007/s00037-018-0168-4
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Copyright Holders: © Springer International Publishing AG, part of Springer Nature 2018

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