Abstract
The area of graph property testing seeks to understand the relation between the global properties of a graph and its local statistics. In the classical model, the local statistics of a graph is defined relative to a uniform distribution over the graph’s vertex set. A graph property \({\cal P}\) is said to be testable if the local statistics of a graph can allow one to distinguish between graphs satisfying \({\cal P}\) and those that are far from satisfying it.
Goldreich recently introduced a generalization of this model in which one endows the vertex set of the input graph with an arbitrary and unknown distribution, and asked which of the properties that can be tested in the classical model can also be tested in this more general setting. We completely resolve this problem by giving a (surprisingly “clean ”) characterization of these properties. To this end, we prove a removal lemma for vertex weighted graphs which is of independent interest.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs, Combinatorica 20 (2000), 451–476.
N. Alon, E. Fischer, I. Newman and A. Shapira, A combinatorial characterization of the testable graph properties: it’s all about regularity, SIAM Journal on Computing 39 (2009), 143–167.
N. Alon and J. Fox, Easily testable graph properties, Combinatorics, Probability and Computing 24 (2015), 646–657.
N. Alon and A. Shapira, A characterization of the (natural) graph properties testable with one-sided error, SIAM Journal on Computing 37 (2008), 1703–1727.
N. Alon and A. Shapira, Every monotone graph property is testable, SIAM Journal on Computing 38 (2008), 505–522.
T. Austin and T. Tao, On the testability and repair of hereditary hypergraph properties, Random Structures & Algorithms 36 (2010), 373–463.
L. Avigad and O. Goldreich, Testing graph blow-up, in Studies in Complexity and Cryptography, Lecture Notes in Computer Science, Vol. 6650, Springer, Heidelberg, 2011, pp. 156–172.
M. Blum, M. Luby and R. Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences 47 (1993), 549–595.
X. Chen, Z. Liu, R. A. Servedio, Y. Sheng and J. Xie, Distribution-free junta testing, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2018, pp. 749–759.
X. Chen and J. Xie, Tight bounds for the distribution-free testing of monotone conjunctions, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2016, pp. 54–71.
D. Conlon and J. Fox, Bounds for graph regularity and removal lemmas, Geometric and Functional Analysis 22 (2012), 1191–1256.
D. Conlon and J. Fox, Graph removal lemmas, in Surveys in Combinatorics, London Mathematical Society Lecture Note Series, Vol. 409, Cambridge University Press, Cambridge, 2013, pp. 1–50.
B. Csaba and A. Pluhár, A weighted regularity lemma with applications, International Journal of Combinatorics (2014), Article no. 602657.
E. Dolev and D. Ron, Distribution-free testing for monomials with a sublinear number of queries, Theory of Computing 7 (2011), 155–176.
L. Gishboliner and A. Shapira, Efficient removal without efficient regularity, Combinatorica 39 (2019), 639–658.
D. Glasner and R. A. Servedio, Distribution-free testing lower bound for basic boolean functions, Theory of Computing 5 (2009), 191–216.
O. Goldreich, Introduction to Property Testing, Cambridge University Press, Cambridge, 2017.
O. Goldreich, Testing graphs in vertex-distribution-free models, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2019, pp. 527–534.
O. Goldreich, S. Goldwasser and D. Ron, Property testing and its connection to learning and approximation, Journal of the ACM 45 (1998), 653–750.
O. Goldreich and D. Ron, Property testing in bounded degree graphs, Algorithmica 32 (2002), 302–343.
O. Goldreich and D. Ron, On proximity-oblivious testing, SIAM Journal on Computing 40 (2011), 534–566.
O. Goldreich and L. Trevisan, Three theorems regarding testing graph properties, Random Structures & Algorithms 23 (2003), 23–57.
S. Halevy and E. Kushilevitz, Distribution-free property testing, in Approximation, Randomization, and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 2764, Springer, Berlin, 2003, pp. 302–317.
S. Kalyanasundaram and A. Shapira, A Wowzer-type lower bound for the strong regularity-lemma, Proceedings of the London Mathematical Society 106 (2013), 621–649.
L. Lovász and B. Szegedy, Testing properties of graphs and functions, Israel Journal of Mathematics 178 (2010), 113–156.
D. Ron, Property testing: A learning theory perspective, Foundations and Trends in Machine Learning 1 (2008), 307–402.
R. Rubinfeld and M. Sudan, Robust characterizations of polynomials with applications to program testing, SIAM Journal on Computing 25 (1996), 252–271.
I. Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, in Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloquia Mathematica Societatis Janos Bolyai, Vol. 18, North-Holland, Amsterdam-New York, 1978, pp. 939–945.
E. Szemerédi, Regular partitions of graphs, in Problèmes combinatoires et théorie des graphes, Colloque International CNRS, Vol. 260, CNRS, Paris, 1978, pp. 399–401.
L. Valiant, A theory of the learnable, Communications of the ACM 27 (1984), 1134–1142.
Acknowledgements
We are grateful to an anonymous referee for spotting a gap in the proof of Theorem 1 in a preliminary version of the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper has appeared in the Proceedings of STOC’ 19.
Supported in part by ERC Starting Grant 633509.
Supported in part by ISF Grant 1028/16 and ERC Starting Grant 633509.
Rights and permissions
About this article
Cite this article
Gishboliner, L., Shapira, A. Testing graphs against an unknown distribution. Isr. J. Math. 245, 787–837 (2021). https://doi.org/10.1007/s11856-021-2228-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-021-2228-8