Authors
Oded Goldreich
Publication date
2019/5/8
Journal
arXiv preprint arXiv:1905.03070
Description
In a recent work (ECCC, TR18-171, 2018), we introduced models of testing graph properties in which, in addition to answers to the usual graph-queries, the tester obtains {\em random vertices drawn according to an arbitrary distribution }. Such a tester is required to distinguish between graphs that have the property and graphs that are far from having the property, {\em where the distance between graphs is defined based on the unknown vertex distribution }. These ("vertex-distribution free" (VDF)) models generalize the standard models in which is postulated to be uniform on the vertex-set, and they were studies both in the dense graph model and in the bounded-degree graph model. The focus of the aforementioned work was on testers, called {\sf strong}, whose query complexity depends only on the proximity parameter . Unfortunately, in the standard bounded-degree graph model, some natural properties such as Bipartiteness do not have strong testers, and others (like cycle-freeness) do not have strong testers of one-sided error (whereas one-sided error was shown inherent to the VDF model). Hence, it was suggested to study general (i.e., non-strong) testers of "sub-linear" complexity. In this work, we pursue the foregoing suggestion, but do so in a model that augments the model presented in the aforementioned work. Specifically, we provide the tester with an evaluation oracle to the unknown distribution , in addition to samples of and oracle access to the tested graph. Our main results are testers for Bipartitness and cycle-freeness, in this augmented model, having complexity that is almost-linear in the square root of the "effective support …
Total citations