{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:59Z","timestamp":1787340239434,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>Tolerant testing is an emerging topic in the field of property testing, which was defined in [M. Parnas, D. Ron, and R. Rubinfeld, J. Comput. System Sci., 72 (2006), pp. 1012\u20131042] and has recently become a very active topic of research. In the general setting, there exist properties that are testable but are not tolerantly testable [E. Fischer and L. Fortnow, Proceedings of the $20$th IEEE Conference on Computational Complexity, 2005, pp. 135\u2013140]. On the other hand, we show here that in the setting of the dense graph model, all testable properties are not only tolerantly testable (which was already implicitly proved in [N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Combinatorica, 20 (2000), pp. 451\u2013476] and [O. Goldreich and L. Trevisan, Random Structures Algorithms, 23 (2003), pp. 23\u201357]), but also admit a constant query size algorithm that estimates the distance from the property up to any fixed additive constant. In the course of the proof we develop a framework for extending Szemer\u00e9di's regularity lemma, both as a prerequisite for formulating what kind of information about the input graph will provide us with the correct estimation, and as the means for efficiently gathering this information. In particular, we construct a probabilistic algorithm that finds the parameters of a regular partition of an input graph using a constant number of queries, and an algorithm to find a regular partition of a graph using a $\\mathrm{TC}_0$ circuit. This, in some ways, strengthens the results of [N. Alon, R. A. Duke, H. Lefmann, V. R\u00f6dl, and R. Yuster, J. Algorithms, 16 (1994), pp. 80\u2013109].<\/jats:p>","DOI":"10.1137\/060652324","type":"journal-article","created":{"date-parts":[[2007,5,25]],"date-time":"2007-05-25T13:18:27Z","timestamp":1180099107000},"page":"482-501","source":"Crossref","is-referenced-by-count":38,"title":["Testing versus Estimation of Graph Properties"],"prefix":"10.1137","volume":"37","author":[{"given":"Eldar","family":"Fischer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2007,5,22]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"N. Alon, E. Fischer, I. Newman, and A. Shapira,\n                      A combinatorial characterization of the testable graph properties: It's all about regularity\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), 2006, pp. 251\u2013260.","DOI":"10.1145\/1132516.1132555"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"N. Alon and A. Shapira,\n                      Every monotone graph property is testable\n                      , in Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), 2005, pp. 128\u2013137.","DOI":"10.1145\/1060590.1060611"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"N. Alon and A. Shapira,\n                      A characterization of the (natural) graph properties testable with one-sided error\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2005, pp. 429\u2013438.","DOI":"10.1109\/SFCS.2005.5"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , 2nd ed., Wiley, New York, 2000.","DOI":"10.1002\/0471722154"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"R8","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 2nd ed., Springer-Verlag, New York, 2000."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20037"},{"key":"R10","first-page":"97","volume":"75","author":"Fischer E.","year":"2001","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970445603"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"E. Fischer and L. Fortnow,\n                      Tolerant versus intolerant testing for Boolean properties\n                      , in Proceedings of the 20th Annual IEEE Conference on Computational Complexity, 2005, pp. 135\u2013140.","DOI":"10.1109\/CCC.2005.30"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"M. Parnas, D. Ron, and R. Rubinfeld,\n                      Tolerant property testing and distance approximation\n                      , J. Comput. System Sci., 72 (2006) pp. 1012\u20131042.","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"R16","unstructured":"D. Ron,\n                      Property testing (a tutorial)\n                      , in Handbook of Randomized Computing, Vol. II, S. Rajasekaran, P. M. Pardalos, J. H. Reif, and J. D. P. Rolim, eds., Kluwer Academic Publishers, Boston, 2001, pp. 597\u2013649."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"R18","unstructured":"E. Szemer\u00e9di,\n                      Regular partitions of graphs\n                      , in Probl\u00e8mes combinatoires et th\u00e9orie des graphes, Colloq. Internat. CNRS 260, J. C. Bermond, J. C. Fournier, M. Las Vergnas, and D. Sotteau, eds., CNRS, Paris, 1978, pp. 399\u2013401."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060652324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:26:28Z","timestamp":1787336788000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060652324"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1137\/060652324"],"URL":"https:\/\/doi.org\/10.1137\/060652324","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}