ECCC-Report TR13-059https://eccc.weizmann.ac.il/report/2013/059Comments and Revisions published for TR13-059en-usTue, 09 Apr 2013 20:52:36 +0300
Paper TR13-059
| Deterministic vs Non-deterministic Graph Property Testing |
Asaf Shapira,
Lior Gishboliner
https://eccc.weizmann.ac.il/report/2013/059A graph property P is said to be testable if one can check if a graph is close or far from satisfying P using few random local inspections. Property P is said to be non-deterministically testable if one can supply a "certificate" to the fact that a graph satisfies P so that once the certificate is given its correctness can be tested. The notion of non-deterministic testing of graph properties was recently introduced by Lovasz and Vesztergombi, who proved that (somewhat surprisingly) a graph property is testable if and only if it is non-deterministically testable. Their proof used graph limits, and so it did not supply any explicit bounds. They thus asked if one can obtain a proof of their result which will supply such bounds. We answer their question positively by proving their result using Szemeredi's regularity lemma.
An interesting aspect of our proof is that it highlights the fact that the regularity lemma can be interpreted as saying that all graphs can be approximated by finitely many "template" graphs. Tue, 09 Apr 2013 20:52:36 +0300https://eccc.weizmann.ac.il/report/2013/059