Tolerant Bipartiteness Testing in Dense Graphs

Abstract

Bipartite testing has been a central problem in the area of property testing since its inception in the seminal work of Goldreich, Goldwasser and Ron [FOCS'96 and JACM'98]. Though the non-tolerant version of bipartite testing has been extensively studied in the literature, the tolerant variant is not well understood. In this paper, we consider the following version of tolerant bipartite testing: Given a parameter \(\varepsilon \in (0,1)\) and access to the adjacency matrix of a graph \(G\), we can decide whether \(G\) is \(\varepsilon\)-close to being bipartite or \(G\) is at least \((2+\Omega(1))\varepsilon\)-far from being bipartite, by performing \(\widetilde{\mathcal{O}}\left(\frac{1}{\varepsilon ^3}\right)\) queries and in \(2^{\widetilde{\mathcal{O}}(1/\varepsilon)}\) time. This improves upon the state-of-the-art query and time complexities of this problem of \(\widetilde{\mathcal{O}}\left(\frac{1}{\varepsilon ^6}\right)\) and \(2^{\widetilde{\mathcal{O}}(1/\varepsilon^2)}\), respectively, from the work of Alon, Fernandez de la Vega, Kannan and Karpinski (STOC'02 and JCSS'03), where \(\widetilde{\mathcal{O}}(\cdot)\) hides a factor polynomial in \(\log \frac{1}{\varepsilon}\).