期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-40
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The graph isomorphism distance between two graphs Gu and Gk is the fraction of entries in the adjacency matrix that has to be changed to make Gu isomorphic to Gk . We study the problem of estimating, up to a constant additive factor, the graph isomorphism distance between two graphs in the query model. In other words, if Gk is a known graph and Gu is an unknown graph whose adjacency matrix has to be accessed by querying the entries, what is the query complexity for testing whether the graph isomorphism distance between Gu and Gk is less than γ1 or more than γ2, where γ1 and γ2 are two constants with 0 ≤ γ1 < γ2 ≤ 1. It is also called the tolerant property testing of graph isomorphism in the dense graph model. The non-tolerant version (where γ1 is 0) has been studied by Fischer and Matsliah (SICOMP’08). In this paper, we study both the upper and lower bounds of tolerant graph isomorphism testing. We prove an upper bound of Oe(n) for this problem. Our upper bound algorithm crucially uses the tolerant testing of the well studied Earth Mover Distance (EMD), as the main subroutine, in a slightly different setting from what is generally studied in property testing literature. Testing tolerant EMD between two probability distributions is equivalent to testing EMD between two multi-sets, where the multiplicity of each element is taken appropriately, and we sample elements from the unknown multi-set with replacement. In this paper, our (main conceptual) contribution is to introduce the problem of (tolerant) EMD testing between multi-sets (over Hamming cube) when we get samples from the unknown multi-set without replacement and to show that this variant of tolerant testing of EMD is as hard as tolerant testing of graph isomorphism between two graphs. Thus, while testing of equivalence between distributions is at the heart of the non-tolerant testing of graph isomorphism, we are showing that the estimation of the EMD over a Hamming cube (when we are allowed to sample without replacement) is at the heart of tolerant graph isomorphism. We believe that the introduction of the problem of testing EMD between multi-sets (when we get samples without replacement) opens an entirely new direction in the world of testing properties of distributions.
