{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,29]],"date-time":"2026-01-29T12:27:54Z","timestamp":1769689674861,"version":"3.49.0"},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2013,7,3]],"date-time":"2013-07-03T00:00:00Z","timestamp":1372809600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>A property of finite graphs is called non-deterministically testable if it has a \u2018certificate\u2019 such that once the certificate is specified, its correctness can be verified by random local testing. In this paper we study certificates that consist of one or more unary and\/or binary relations on the nodes, in the case of dense graphs. Using the theory of graph limits, we prove that non-deterministically testable properties are also deterministically testable.<\/jats:p>","DOI":"10.1017\/s0963548313000205","type":"journal-article","created":{"date-parts":[[2013,7,3]],"date-time":"2013-07-03T15:06:54Z","timestamp":1372864014000},"page":"749-762","source":"Crossref","is-referenced-by-count":10,"title":["Non-Deterministic Graph Property Testing"],"prefix":"10.1017","volume":"22","author":[{"given":"L\u00c1SZL\u00d3","family":"LOV\u00c1SZ","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KATALIN","family":"VESZTERGOMBI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,7,3]]},"reference":[{"key":"S0963548313000205_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"S0963548313000205_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-007-0599-6"},{"key":"S0963548313000205_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.05.002"},{"key":"S0963548313000205_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16367-8"},{"key":"S0963548313000205_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33700-8_18"},{"key":"S0963548313000205_ref7","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2012.176.1.2"},{"key":"S0963548313000205_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"S0963548313000205_ref18","unstructured":"Lov\u00e1sz L. and Szegedy B. Limits of compact decorated graphs. arXiv:1010.5155"},{"key":"S0963548313000205_ref20","volume-title":"Theory of the Integral","author":"Saks","year":"1964"},{"key":"S0963548313000205_ref19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"S0963548313000205_ref10","doi-asserted-by":"crossref","unstructured":"Fischer E. and Newman I. (2005) Testing versus estimation of graph properties. In Proc. 37th ACM Symposium on the Theory of Computing, pp. 138\u2013146.","DOI":"10.1145\/1060590.1060612"},{"key":"S0963548313000205_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-010-0060-7"},{"key":"S0963548313000205_ref14","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/060"},{"key":"S0963548313000205_ref4","doi-asserted-by":"crossref","unstructured":"Arora S. , Karger D. and Karpinski M. (1995) Polynomial time approximation schemes for dense instances of NP-hard problems. In Proc. 27th ACM Symposium on the Theory of Computing, pp. 284\u2013293.","DOI":"10.1145\/225058.225140"},{"key":"S0963548313000205_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"S0963548313000205_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.07.008"},{"key":"S0963548313000205_ref9","first-page":"97","article-title":"The art of uninformed decisions: A primer to property testing. The Computational Complexity Column of the","volume":"75","author":"Fischer","year":"2001","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"S0963548313000205_ref8","unstructured":"Elek G. and Szegedy B. Limits of hypergraphs, removal and regularity lemmas: A non-standard approach. arXiv:0705.2179"},{"key":"S0963548313000205_ref1","doi-asserted-by":"publisher","DOI":"10.1137\/06064888X"},{"key":"S0963548313000205_ref3","doi-asserted-by":"crossref","unstructured":"Alon N. , Fischer E. , Newman I. and Shapira A. (2006) A combinatorial characterization of the testable graph properties: It's all about regularity. In Proc. 38th ACM Symposium on the Theory of Computing: STOC, pp. 251\u2013260.","DOI":"10.1145\/1132516.1132555"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,2]],"date-time":"2023-07-02T21:34:08Z","timestamp":1688333648000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000205\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,3]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["S0963548313000205"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000205","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7,3]]}}}