zbMATH — the first resource for mathematics

Testing graph blow-up. (English) Zbl 1343.68286
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 156-172 (2011).
Summary: Referring to the query complexity of testing graph properties in the adjacency matrix model, we advance the study of the class of properties that can be tested non-adaptively within complexity that is inversely proportional to the proximity parameter. Arguably, this is the lowest meaningful complexity class in this model, and we show that it contains a very natural class of graph properties. Specifically, for every fixed graph \(H\), we consider the set of all graphs that are obtained by a (possibly unbalanced) blow-up of \(H\). We show a non-adaptive tester of query complexity \(\widetilde{O}(1 / \epsilon )\) that distinguishes graphs that are a blow-up of \(H\) from graphs that are \(\epsilon \)-far from any such blow-up.
For the entire collection see [Zbl 1220.68005].

68W20 Randomized algorithms
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient Testing of Large Graphs. Combinatorica 20, 451–476 (2000) · Zbl 1052.68096
[2] Alon, N., Fischer, E., Newman, I., Shapira, A.: A Combinatorial Characterization of the Testable Graph Properties: It’s All About Regularity. In: 38th STOC, pp. 251–260 (2006) · Zbl 1301.05354
[3] Alon, N., Shapira, A.: A Characterization of Easily Testable Induced Subgraphs. Combinatorics Probability and Computing 15, 791–805 (2006) · Zbl 1318.68191
[4] Avigad, L.: On the Lowest Level of Query Complexity in Testing Graph Properties. Master thesis, Weizmann Institute of Science (December 2009)
[5] Canetti, R., Even, G., Goldreich, O.: Lower Bounds for Sampling Algorithms for Estimating the Average. In: IPL, vol. 53, pp. 17–25 (1995) · Zbl 0875.68529
[6] Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM, 653–750 (July 1998) · Zbl 1065.68575
[7] Goldreich, O., Krivelevich, M., Newman, I., Rozenberg, E.: Hierarchy theorems for property testing. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol. 5687, pp. 504–519. Springer, Heidelberg (2009) · Zbl 1255.68290
[8] Goldreich, O., Ron, D.: Algorithmic Aspects of Property Testing in the Dense Graphs Model. ECCC, TR08-039 (2008)
[9] Goldreich, O., Ron, D.: On Proximity Oblivious Testing. ECCC, TR08-041 (2008), Extended Abstract in the Proceedings of the 41st STOC (2009) · Zbl 1304.05134
[10] Goldreich, O., Trevisan, L.: Three theorems regarding testing graph properties. Random Structures and Algorithms 23(1), 23–57 (2003) · Zbl 1048.68062
[11] Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing 25(2), 252–271 (1996) · Zbl 0844.68062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.