Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-118 | 5th August 2020 00:41

On Testing Asymmetry in the Bounded Degree Graph Model

RSS-Feed




TR20-118
Authors: Oded Goldreich
Publication: 5th August 2020 00:41
Downloads: 79
Keywords: 


Abstract:

We consider the problem of testing asymmetry in the bounded-degree graph model, where a graph is called asymmetric if the identity permutation is its only automorphism. Seeking to determine the query complexity of this testing problem, we provide partial results. Considering the special case of $n$-vertex graphs with connected components of size at most $s(n)=\Omega(\log n)$, we show that the query complexity of $\epsilon$-testing asymmetry (in this case) is at most $O({\sqrt n}\cdot s(n)/\epsilon)$, whereas the query complexity of $o(1/s(n))$-testing asymmetry (in this case) is at least $\Omega({\sqrt{n/s(n)}})$.

In addition, we show that testing asymmetry in the dense graph model is almost trivial.



ISSN 1433-8092 | Imprint