## Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model

#### Webpage for a paper by Oded Goldreich

#### Abstract

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
*random vertices drawn according to an arbitrary distribution $D$*.
Such a tester is required to distinguish between graphs that
have the property and graphs that are far from having the property,
*where the distance between graphs is defined based on the
unknown vertex distribution $D$*.
These (``vertex-distribution free'' (VDF)) models
generalize the standard models
in which $D$ 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 *strong*,
whose query complexity depends only on the proximity parameter $\epsilon$.
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 $D$, in addition to samples of $D$
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 size'' of $D$.

#### Material available on-line

- First version posted:
May 2019.
- Revisions: none yet

Back to
either Oded Goldreich's homepage
or general list of papers.