## On Testing Asymmetry in the Bounded Degree Graph Model

#### Webpage for a paper by Oded Goldreich

#### 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.

**Note:**
The versions of 2020 present a weaker result.
Specifically, in January 2021 the result was generalized
to offer lower bounds for any value of the proximity parameter.
This is supported by the new Proposition 6.

#### Material available on-line

Back to
either Oded Goldreich's homepage
or general list of papers.