论文标题
密集图中的耐受性会测试
Tolerant Bipartiteness Testing in Dense Graphs
论文作者
论文摘要
自从戈德里希（Goldreich），戈德瓦瑟（Goldwasser）和罗恩（Ron）开创性工作以来，两部分测试一直是物业测试领域的核心问题[focs'96和jacm'98]。尽管在文献中已经广泛研究了两分性测试的非耐受性版本，但耐受性变体尚未得到充分了解。在本文中，我们考虑以下版本的耐受性两分性测试：给定（0,1）$中的参数$ \ varepsilon \，并访问图$ g $的邻接矩阵，我们可以决定$ g $是$ \ varepsilon $ -close是bipartite $ close y bipartite bipartite还是$ g $ co $ co $至少是$ $（$ $ $（1）$（2+（2+ω）双方，通过执行$ \ widetilde {\ Mathcal {o}} \ left（\ frac {1} {\ varepsilon ^3} \ right）$ QUERIES $ QUERIES，in $ 2 ^{\ wideTilde {\ wideTilde {\ wideTilde {\ Mathcal {\ Mathcal {o}}}（1/\ vareps} $ time）这是$ \ widetilde {\ Mathcal {o}} \ left（\ frac {1} {\ varepsilon^6} \ right）$的最新查询和时间复杂性的改善从阿隆（Alon）的作品中，费尔南德斯·德拉维加（Fernandez de la Vega），坎南（Kannan）和卡尔平斯基（Karpinski）（stoc'02和jcss'03），其中$ \ widetilde {\ nathcal {o}}}（\ cdot）$ hides $ hides prominalial in $ \\ log \ frac {1} 1} {\ varps =
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+Ω(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}$.
