Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-034 | 9th March 2021 11:13

Robust Self-Ordering versus Local Self-Ordering


Authors: Oded Goldreich
Publication: 9th March 2021 11:13
Downloads: 245


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.

We consider the relation between these two notions in two regimes: The bounded-degree graph regime, where oracle access to a graph means oracle access to its incidence function, and the dense graph regime, where oracle access to the graph means access to its adjacency predicate.

We show that, {\em in the bounded-degree regime}, robustly self-ordering and local self-ordering are almost orthogonal; that is, even extremely strong versions of one notion do not imply very weak versions of the other notion.
Specifically, we present very efficient local self-ordering procedures for graphs that possess derangements that are almost automorphisms (i.e., a single incidence is violated).
One the other hand, we show robustly self-ordered graphs having no local self-ordering procedures even when allowing a number of queries that is a square root of the graph's size.

{\em In the dense graph regime}, local self-ordering procedures are shown to yield a quantitatively weaker version of the robust self-ordering condition, in which the said proportion is off by a factor that is related to the query complexity of the local self-ordering procedure. Furthermore, we show that this quantitatively loss is inherent.
On the other hand, we show how to transform any robustly self-ordered graph
into one having a local self-ordering procedure, while preserving the robustness condition. Combined with prior work, this yields explicit constructions of graphs that are both robustly and locally self-ordered, and an application to property testing.

ISSN 1433-8092 | Imprint