{"id":183737,"date":"2006-01-27T00:00:00","date_gmt":"2009-10-31T12:59:22","guid":{"rendered":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/msr-research-item\/a-combinatorial-characterization-of-the-testable-graph-properties-its-all-about-regularity\/"},"modified":"2024-10-02T07:56:49","modified_gmt":"2024-10-02T14:56:49","slug":"a-combinatorial-characterization-of-the-testable-graph-properties-its-all-about-regularity","status":"publish","type":"msr-video","link":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/video\/a-combinatorial-characterization-of-the-testable-graph-properties-its-all-about-regularity\/","title":{"rendered":"A Combinatorial Characterization of the Testable Graph Properties: It&#8217;s All About Regularity"},"content":{"rendered":"<div class=\"asset-content\">\n<p>A common thread in all the recent results concerning testing dense graphs is the use of Szemer\u00e9di&#8217;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 Szemeredi- 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 Szemeredi-partitions. This means that in some sense, testing for Szemeredi-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 first raised in the 1996 paper of Goldreich, Goldwasser and Ron that initiated the study of graph property-testing. This characterization also gives an intuitive explanation as to what makes a graph property testable.<\/p>\n<p>Joint work with N. Alon, E. Fischer and I. Newman.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>A common thread in all the recent results concerning testing dense graphs is the use of Szemer\u00e9di&#8217;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 Szemeredi- partition is testable with a constant number of queries. [&hellip;]<\/p>\n","protected":false},"featured_media":195170,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_hide_image_in_river":0,"footnotes":""},"research-area":[13547],"msr-video-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-session-type":[],"msr-impact-theme":[],"msr-pillar":[],"msr-episode":[],"msr-research-theme":[],"class_list":["post-183737","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-research-area-systems-and-networking","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/fCd9hOtJwwc","msr_secondary_video_url":"","msr_video_file":"http:\/\/0","_links":{"self":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/183737","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":1,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/183737\/revisions"}],"predecessor-version":[{"id":1089573,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/183737\/revisions\/1089573"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/media\/195170"}],"wp:attachment":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/media?parent=183737"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=183737"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=183737"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=183737"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=183737"},{"taxonomy":"msr-session-type","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-session-type?post=183737"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=183737"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=183737"},{"taxonomy":"msr-episode","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-episode?post=183737"},{"taxonomy":"msr-research-theme","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-theme?post=183737"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}