ECCC-Report TR21-034https://eccc.weizmann.ac.il/report/2021/034Comments and Revisions published for TR21-034en-usTue, 09 Mar 2021 11:13:43 +0200
Paper TR21-034
| Robust Self-Ordering versus Local Self-Ordering |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2021/034We 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.
Tue, 09 Mar 2021 11:13:43 +0200https://eccc.weizmann.ac.il/report/2021/034