Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR21-034 | 9th March 2021 11:13

#### Robust Self-Ordering versus Local Self-Ordering

TR21-034
Authors: Oded Goldreich
Publication: 9th March 2021 11:13
Keywords:

Abstract:

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 $G$, denoted $G'$, and a vertex $v$ in $G'$, and is required to identify the name (or location) of $v$ in $G$, while making few (i.e., polylogarithmically many) queries to $G'$.
A graph $G=(V,E)$ is {\em robustly self-ordered} if the size of the symmetric difference between $E$ and the edge-set of the graph obtained by permuting $V$ using any permutation $\pi:V\to V$ is proportional to the number of non-fixed-points of $\pi$ and to the maximal degree of $G$; that is, any permutation of the vertices that displaces $t$ vertices must displace'' $\Omega(t\cdot d)$ edges, where $d$ is the maximal degree of the graph.