Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SYMMETRIC GRAPHS:
Reports tagged with Symmetric graphs:
TR20-118 | 5th August 2020
Oded Goldreich

On Testing Asymmetry in the Bounded Degree Graph Model

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




ISSN 1433-8092 | Imprint