ECCC-Report TR20-118https://eccc.weizmann.ac.il/report/2020/118Comments and Revisions published for TR20-118en-usThu, 01 Jul 2021 18:19:40 +0300
Revision 4
| On Testing Asymmetry in the Bounded Degree Graph Model |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2020/118#revision4We 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.
Thu, 01 Jul 2021 18:19:40 +0300https://eccc.weizmann.ac.il/report/2020/118#revision4
Revision 3
| On Testing Asymmetry in the Bounded Degree Graph Model |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2020/118#revision3We 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.
Sat, 30 Jan 2021 14:06:43 +0200https://eccc.weizmann.ac.il/report/2020/118#revision3
Revision 2
| On Testing Asymmetry in the Bounded Degree Graph Model |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2020/118#revision2We 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.Sat, 09 Jan 2021 11:01:53 +0200https://eccc.weizmann.ac.il/report/2020/118#revision2
Revision 1
| On Testing Asymmetry in the Bounded Degree Graph Model |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2020/118#revision1We 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.
Fri, 08 Jan 2021 14:53:51 +0200https://eccc.weizmann.ac.il/report/2020/118#revision1
Paper TR20-118
| On Testing Asymmetry in the Bounded Degree Graph Model |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2020/118We 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.
Wed, 05 Aug 2020 00:41:44 +0300https://eccc.weizmann.ac.il/report/2020/118