Article

A combinatorial characterization of the testable graph properties: it's all about regularity

Authors:

Asaf ShapiraAuthors Info & Claims

STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

Pages 251 - 260

https://doi.org/10.1145/1132516.1132555

Published: 21 May 2006 Publication History

Abstract

A common thread in recent results concerning the testing of dense graphs is the use of Szemerédi's regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first result is that the property defined by having any given Szemerédi-partition is testable with a constant number of queries. Our second and main result is a purely combinatorial characterization of the graph properties that are testable with a constant number of queries. This characterization (roughly) says that a graph property P can be tested with a constant number of queries if and only if testing P can be reduced to testing the property of satisfying one of finitely many Szemerédi-partitions. This means that in some sense, testing for Szemerédi-partitions is as hard as testing any testable graph property. We thus resolve one of the main open problems in the area of property-testing, which was raised in the 1996 paper of Goldreich, Goldwasser and Ron [25] that initiated the study of graph property-testing. This characterization also gives an intuitive explanation as to what makes a graph property testable.

References

[1]

N. Alon, R. A. Duke, H. Lefmann, V. Rödl and R. Yuster, The algorithmic aspects of the Regularity Lemma, J. of Algorithms 16 (1994), 80--109.]]

Digital Library

[2]

N. Alon, S. Dar, M. Parnas and D. Ron, Testing of clustering, Proc. 41st IEEE FOCS, IEEE (2000), 240--250.]]

Digital Library

[3]

N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs, Proc. of 40th FOCS, New York, NY, IEEE (1999), 656--666. Also: Combinatorica 20 (2000), 451--476.]]

Digital Library

[4]

N. Alon, M. Krivelevich, I. Newman and M. Szegedy, Regular languages are testable with a constant number of queries, SICOMP 30 (2001), 1842--1862.]]

Digital Library

[5]

N. Alon and M. Krivelevich, Testing k-colorability, SIAM J. Discrete Math., 15 (2002), 211--227.]]

Digital Library

[6]

N. Alon and A. Shapira, Every monotone graph property is testable, Proc. of STOC 2005, 128--137.]]

Digital Library

[7]

N. Alon and A. Shapira, A characterization of the (natural) graph properties testable with one-sided error, Proc. of FOCS 2005, 429--438.]]

Digital Library

[8]

M. Ben-Or, D. Coppersmith, M. Luby and R. Rubinfeld, Non-abelian homomorphism testing, and distributions close to their self-convolutions, Proc. of RANDOM 2004, 273--285.]]

[9]

E. Ben-Sasson, P. Harsha and S. Raskhodnikova, Some 3-CNF properties are hard to test, Proc. of STOC 2003, 345--354.]]

Digital Library

[10]

M. Blum, M. Luby and R. Rubinfeld, Self-testing/correcting with applications to numerical problems, JCSS 47 (1993), 549--595.]]

Digital Library

[11]

C. Borgs, J. Chayes, L. Lovász, V.T. Sós, B. Szegedy and K. Vesztergombi: Graph limits and parameter testing, Proc. of STOC 2006.]]

Digital Library

[12]

A. Czumaj, C. Sohler and M. Ziegler, Property testing in computational geometry, Proc. of ESA 2000, 155--166.]]

Digital Library

[13]

A. Czumaj and C. Sohler, Abstract combinatorial programs and efficient property testers, SICOMP 34 (2005), 580--615.]]

Digital Library

[14]

E. Fischer, Testing graphs for colorability properties, Proc. of the 12th SODA (2001), 873--882.]]

Digital Library

[15]

E. Fischer, The art of uninformed decisions: A primer to property testing, The Computational Complexity Column of The Bulletin of the EATCS 75 (2001), 97--126.]]

[16]

E. Fischer, The difficulty of testing for isomorphism against a graph that is given in advance, SICOMP, 34, 1147--1158.]]

Digital Library

[17]

E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky, Testing juntas, JCSS 68 (2004), 753--787. Also, Proc. of FOCS (2002), 103--112.]]

Digital Library

[18]

E. Fischer and I. Newman, Testing versus estimation of graph properties, Proc. of STOC 2005, 138--146.]]

Digital Library

[19]

E. Fischer, I. Newman and J. Sgall, Functions that have read-twice constant width branching programs are not necessarily testable, Random Struc. and Alg., in press.]]

Digital Library

[20]

E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld and A. Samorodnitsky, Monotonicity testing over general poset domains, Proc. of STOC (2002), 474--483.]]

Digital Library

[21]

K. Friedl, G. Ivanyos and M. Santha, Efficient testing of groups, Proc. of STOC (2005), 157--166.]]

Digital Library

[22]

A. Frieze and R. Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), 175--220.]]

[23]

O. Goldreich, Combinatorial property testing - a survey, In: Randomization Methods in Algorithm Design (P. Pardalos, S. Rajasekaran and J. Rolim eds.), AMS-DIMACS (1998), 45--60.]]

[24]

O. Goldreich, Contemplations on testing graph properties, manuscript, 2005.]]

[25]

O. Goldreich, S. Goldwasser and D. Ron, Property testing and its connection to learning and approximation, JACM 45(4): 653--750 (1998).]]

Digital Library

[26]

O. Goldreich and L. Trevisan, Three theorems regarding testing graph properties, Random Structures and Algorithms, 23 (2003), 23--57.]]

Digital Library

[27]

O. Goldreich and D. Ron, Property Testing in Bounded-Degree Graphs, Proc. of STOC 1997, 406--415.]]

Digital Library

[28]

J. Komlós and M. Simonovits, Szemerédi's Regularity Lemma and its applications in graph theory. In: Combinatorics, Paul Erdös is Eighty, Vol II (D. Miklós, V. T. Sós, T. Szönyi eds.), János Bolyai Math. Soc., Budapest (1996), 295--352.]]

[29]

L. Lovász and B. Szegedy, Graph limits and testing hereditary graph properties, manuscript, 2005.]]

[30]

I. Newman, Testing of functions that have small width branching programs, Proc. of FOCS 2000, 251--258.]]

Digital Library

[31]

M. Parnas and D. Ron, Testing the diameter of graphs, Random structures and algorithms, 20 (2002), 165--183.]]

Digital Library

[32]

M. Parnas, D. Ron and R. Rubinfeld, Testing membership in parenthesis languages, Random Struct. and Algorithms 22 (2003), 98--138.]]

Digital Library

[33]

V. Rödl and R. Duke, On graphs with small subgraphs of large chromatic number, Graphs and Combinatorics 1 (1985), 91--96.]]

Digital Library

[34]

Property testing, in: P. M. Pardalos, S. Rajasekaran, J. Reif and J. D. P. Rolim, editors, Handbook of Randomized Computing, Vol. II, Kluwer Academic Publishers, 2001, 597--649.]]

[35]

Robust characterization of polynomials with applications to program testing, SICOMP 25 (1996), 252--271.]]

Digital Library

[36]

E. Szemerédi, Regular partitions of graphs, In: Proc. Colloque Inter. CNRS (J. C. Bermond, J. C. Fournier, M. Las Vergnas and D. Sotteau, eds.), 1978, 399--401.]]

Cited By

Norros IReittu HBazsó F(2022)On model selection for dense stochastic block modelsAdvances in Applied Probability10.1017/apr.2021.2954:1(202-226)Online publication date: 14-Jan-2022
https://doi.org/10.1017/apr.2021.29
Goldreich O(2019)Hierarchy Theorems for Testing Properties in Size-Oblivious Query ComplexityComputational Complexity10.1007/s00037-019-00187-228:4(709-747)Online publication date: 1-Dec-2019
https://dl.acm.org/doi/10.1007/s00037-019-00187-2
Dey PBhattacharyya AWeiss GYolum PBordini RElkind E(2015)Sample Complexity for Winner Prediction in ElectionsProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2773334(1421-1430)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2773334
Show More Cited By

Index Terms

A combinatorial characterization of the testable graph properties: it's all about regularity
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Every monotone graph property is testable
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

A graph property is called monotone if it is closed under taking (not necessarily induced) subgraphs (or, equivalently, if it is closed under removal of edges and vertices). Many monotone graph properties are some of the most well-studied properties in ...
Testing versus estimation of graph properties
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

The topic of tolerant property testing, that of distinguishing input instances that are far from satisfying a property from those that are close enough to satisfying it (as opposed to distinguishing the far instances only from the satisfying instances), ...
A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity

A common thread in all of the recent results concerning the testing of dense graphs is the use of Szemerédi's regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first result is that the property defined by having ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

May 2006

786 pages

ISBN:1595931341

DOI:10.1145/1132516

Program Chair:
Jon Kleinberg
Cornell University, Ithaca, NY

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 May 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC06

Sponsor:

STOC06: Symposium on Theory of Computing

May 21 - 23, 2006

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

79
Total Citations
View Citations
508
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)4

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Norros IReittu HBazsó F(2022)On model selection for dense stochastic block modelsAdvances in Applied Probability10.1017/apr.2021.2954:1(202-226)Online publication date: 14-Jan-2022
https://doi.org/10.1017/apr.2021.29
Goldreich O(2019)Hierarchy Theorems for Testing Properties in Size-Oblivious Query ComplexityComputational Complexity10.1007/s00037-019-00187-228:4(709-747)Online publication date: 1-Dec-2019
https://dl.acm.org/doi/10.1007/s00037-019-00187-2
Dey PBhattacharyya AWeiss GYolum PBordini RElkind E(2015)Sample Complexity for Winner Prediction in ElectionsProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2773334(1421-1430)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2773334
Gur TRothblum RRoughgarden T(2015)Non-Interactive Proofs of ProximityProceedings of the 2015 Conference on Innovations in Theoretical Computer Science10.1145/2688073.2688079(133-142)Online publication date: 11-Jan-2015
https://dl.acm.org/doi/10.1145/2688073.2688079
Bhattacharyya AXie N(2015)Lower bounds for testing triangle-freeness in Boolean functionsComputational Complexity10.1007/s00037-014-0092-124:1(65-101)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1007/s00037-014-0092-1
Bhattacharyya AFischer ELovett SKhanna S(2013)Testing low complexity affine-invariant propertiesProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627914(1337-1355)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627914
Bhattacharyya A(2013)Guest columnACM SIGACT News10.1145/2556663.255667844:4(53-72)Online publication date: 10-Dec-2013
https://dl.acm.org/doi/10.1145/2556663.2556678
Bhattacharyya AFischer EHatami HHatami PLovett SBoneh DRoughgarden TFeigenbaum J(2013)Every locally characterized affine-invariant property is testableProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488662(429-436)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488662
LOVÁSZ LVESZTERGOMBI K(2013)Non-Deterministic Graph Property TestingCombinatorics, Probability and Computing10.1017/S096354831300020522:5(749-762)Online publication date: 3-Jul-2013
https://doi.org/10.1017/S0963548313000205
Bhattacharyya AYoshida Y(2013)An algebraic characterization of testable boolean CSPsProceedings of the 40th international conference on Automata, Languages, and Programming - Volume Part I10.1007/978-3-642-39206-1_11(123-134)Online publication date: 8-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39206-1_11
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents