Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Asymmetric graphs:
TR20-118 | 5th August 2020
Oded Goldreich

On Testing Asymmetry in the Bounded Degree Graph Model

Revisions: 4

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

TR20-149 | 29th September 2020
Oded Goldreich, Avi Wigderson

Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing

Revisions: 2

A graph $G$ is called {\em self-ordered}\/ (a.k.a asymmetric) if the identity permutation is its only automorphism.
Equivalently, there is a unique isomorphism from $G$ to any graph that is isomorphic to $G$.
We say that $G=(V,E)$ is {\em robustly self-ordered}\/ if the size of the symmetric difference ... more >>>

TR21-034 | 9th March 2021
Oded Goldreich

Robust Self-Ordering versus Local Self-Ordering

We study two notions that refers to asymmetric graphs, which we view as graphs having a unique ordering that can be reconstructed by looking at an unlabeled version of the graph.

A {\em local self-ordering} procedure for a graph $G$ is given oracle access to an arbitrary isomorphic copy of ... more >>>

ISSN 1433-8092 | Imprint