[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity

  • Published:
computational complexity Aims and scope Submit manuscript

Abstract

Focusing on property testing tasks that have query complexity that is independent of the size of the tested object (i.e., depends on the proximity parameter only), we prove the existence of a rich hierarchy of the corresponding complexity classes. That is, for essentially any function \(q : (0, 1] \rightarrow \mathbb{N}\), we prove the existence of properties for which \(\epsilon\)-testing has query complexity \(\Theta(q(\Theta(\epsilon)))\). Such results are proved in three standard domains that are often considered in property testing: generic functions, adjacency predicates describing (dense) graphs, and incidence functions describing bounded-degree graphs.

These results complement hierarchy theorems of Goldreich, Krivelevich, Newman, and Rozenberg (Computational Complexity, 2012), which refer to the dependence of the query complexity on the size of the tested object, and focus on the case that the proximity parameter is set to some small positive constant. We actually combine both flavors and get tight results on the query complexity of testing when allowing the query complexity to depend on both the size of the object and the proximity parameter.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Similar content being viewed by others

References

  • Alon, N.: Testing subgraphs of large graphs. Random Structures and Algorithms, Vol. 21, 359–370 (2002)

    Article  MathSciNet  Google Scholar 

  • N. Alon, E. Fischer, I. Newman, and A. Shapira. A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity. In 38th STOC, pages 251–260, 2006

  • Alon, N., Shapira, A.: Testing subgraphs in directed graphs. JCSS, Vol. 69, 354–482 (2004)

    Google Scholar 

  • Alon, N., Shapira, A.: Every Monotone Graph Property is Testable. SIAM Journal on Computing, Vol. 38, 505–522 (2008)

    Article  MathSciNet  Google Scholar 

  • I. Benjamini, O. Schramm, and A. Shapira. Every Minor-Closed Property of Sparse Graphs is Testable. In 40th STOC, pages 393–402, 2008

  • Blum, M., Luby, M., Rubinfeld, R.: Self-Testing/Correcting with Applications to Numerical Problems. JCSS, Vol. 47(3), 549–595 (1993)

    MathSciNet  MATH  Google Scholar 

  • A. Bogdanov, K. Obata, and L. Trevisan. A lower bound for testing 3-colorability in bounded-degree graphs. In 43rd FOCS, pages 93–102, 2002

  • L. Gishboliner and A. Shapira. A Generalized Turan Problem and its Applications. ECCC, TR18-007, 2018

  • O. Goldreich. Introduction to Property Testing. Cambridge University Press, 2017.

  • O. Goldreich. Flexible models for testing graph properties. ECCC, TR18-104, 2018

  • O. Goldreich. Testing Graphs in Vertex-Distribution-Free Models. ECCC, TR18-171, 2018

  • O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. Journal of the ACM, pages 653–750, July 1998

    Article  MathSciNet  Google Scholar 

  • Goldreich, O., Krivelevich, M., Newman, I., Rozenberg, E.: Hierarchy Theorems for Property Testing. Computational Complexity, Vol. 21(1), 129–192 (2012)

    Article  MathSciNet  Google Scholar 

  • Goldreich, O., Ron, D.: Property Testing in Bounded Degree Graphs. Algorithmica, Vol. 32(2), 302–343 (2002)

    Article  MathSciNet  Google Scholar 

  • Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing 25(2), 252–271 (1996)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This research was partially supported by the Israel Science Foundation (grants No. 671/13 and 1146/18).

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Oded Goldreich.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Goldreich, O. Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity. comput. complex. 28, 709–747 (2019). https://doi.org/10.1007/s00037-019-00187-2

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00037-019-00187-2

Keywords

Subject classification

Navigation