This work introduces a natural conjecture (see abstract below), which allows to reduce testing bipartitness (in the dense graph model) to testing the same when the proximity parameter equal the reciprocal of the number of vertices. In other words, the general testing problem (of Bipartiteness) is (conditionally) reduced to the following problem, which is of natural appeal:

Given oracle access to the adjacency matrix of an $n$-vertex graph, determine whether the graph is bipartite or that at least $n$ edges must be omitted from the graph to make it bipartite.The current work shows that this problem has query complexity $O(n^c)$, for some $c<2$ (my guess is that $c=1.9$ will do). In the special case where all vertices in the graph have small degree (i.e., at most polylogarithmic degree), this problem is known to have query complexity $\tildeO(n^{3/2})$, see [Gonen and Ron, RANDOM 2007]. On the other hand, a lower bound of $Omega(n^{3/2})$ is known, even in the special case of low degrees, see [Bogdanov and Trevisan, CCC 2004].

The question is what is the query complexity of randomized algorithms that solve this problem, and specifically for one-sided error ones.

Indeed, I think that the above description provides a more applealing description to the contents of the paper than the description provided in the abstract (below) and in the paper. That is, with all due respect to the conjecture (which is established in the case of almost regular graphs) and its potential impact on testing biaprtiteness in general, I find the problem highlighted above and the progress made on it even more appealing. Regarding the gap between adaptive and nonadaptive testers, other examples are/were known (e.g., for testing other properties such as being a collection of cliques).

Alon and Krivelevich (SIAM J. Discrete Math. 15(2): 211-227 (2002)) show that if a graph is {\epsilon}-far from bipartite, then the subgraph induced by a random subset of O(1/{\epsilon}) vertices is bipartite with high probability. We conjecture that the induced subgraph is {\tildeOmega}({\epsilon})-far from bipartite with high probability. Gonen and Ron (RANDOM 2007) proved this conjecture in the case when the degrees of all vertices are at most O({\epsilon}n). We give a more general proof that works for any d-regular (or almost d-regular) graph for arbitrary degree d. Assuming this conjecture, we prove that bipartiteness is testable with one-sided error in time O(1/{\epsilon}^c), where c is a constant strictly smaller than two, improving upon the tester of Alon and Krivelevich. As it is known that non-adaptive testers for bipartiteness require {\Omega}(1/{\epsilon}^2) queries (Bogdanov and Trevisan, CCC 2004), our result shows, assuming the conjecture, that adaptivity helps in testing bipartiteness.

Back to list of Oded's choices.