Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #4 to TR20-118 | 1st July 2021 18:19

#### On Testing Asymmetry in the Bounded Degree Graph Model

Revision #4
Authors: Oded Goldreich
Accepted on: 1st July 2021 18:19
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.
(1) The query complexity of $O(1/\log n)$-testing asymmetry of $n$-vertex graphs is ${\widetilde\Omega}({\sqrt{n/\log n}})$, even if the tested graph is guaranteed to consist of connected components of size $O(\log n)$.
(2) For $s(n)=\Omega(\log n)$, the query complexity of $\e$-testing the set of asymmetric $n$-vertex graphs in which each connected component has size at most $s(n)$ is at most $O({\sqrt n}\cdot s(n)/\e)$ and at least $\Omega({\sqrt{n^{1-O(\e)}/s(n)}})$.

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

Changes to previous version:

Reframing and restructuring the results.

Revision #3 to TR20-118 | 30th January 2021 14:06

#### On Testing Asymmetry in the Bounded Degree Graph Model

Revision #3
Authors: Oded Goldreich
Accepted on: 30th January 2021 14:06
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)$
and at least $\Omega({\sqrt{n^{1-O(\epsilon)}/s(n)}})$. In particular, the query complexity of $o(1/s(n))$-testing asymmetry is at least $\Omega({\sqrt{n/s(n)}})$.

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

Changes to previous version:

Clarifying the proof of Prop 7.

Revision #2 to TR20-118 | 9th January 2021 11:01

#### On Testing Asymmetry in the Bounded Degree Graph Model

Revision #2
Authors: Oded Goldreich
Accepted on: 9th January 2021 11:01
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)$ and at least $\Omega({\sqrt{n^{1-O(\epsilon)}/s(n)}})$. In particular, the query complexity of $o(1/s(n))$-testing asymmetry
is at least $\Omega({\sqrt{n/s(n)}})$.

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

Changes to previous version:

Correcting inaccuracies introduced in yesterday's revision.

Revision #1 to TR20-118 | 8th January 2021 14:53

#### On Testing Asymmetry in the Bounded Degree Graph Model

Revision #1
Authors: Oded Goldreich
Accepted on: 8th January 2021 14:53
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 $\e$-testing asymmetry (in this case) is at most $O({\sqrt n}\cdot s(n)/\e)$ and at least $\Omega({\sqrt{n^{1-O(\e)}/s(n)}})$. In particular, the query complexity of $o(1/s(n))$-testing asymmetry
is at least $\Omega({\sqrt{n/s(n)}})$.

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

Changes to previous version:

The result was generalized to offer lower bounds for any value of the proximity parameter. This is supported by the new Proposition 6.

### Paper:

TR20-118 | 5th August 2020 00:41

#### On Testing Asymmetry in the Bounded Degree Graph Model

TR20-118
Authors: Oded Goldreich
Publication: 5th August 2020 00:41
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)}})$.