Oded Goldreich ; Avi Wigderson - Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing

theoretics:8788 - TheoretiCS, December 21, 2022, Volume 1 - https://doi.org/10.46298/theoretics.22.1
Robustly Self-Ordered Graphs: Constructions and Applications to Property TestingArticle

Authors: Oded Goldreich ; Avi Wigderson

    A graph $G$ is called 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 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$. In this work, we initiate the study of the structure, construction and utility of robustly self-ordered graphs. We show that robustly self-ordered bounded-degree graphs exist (in abundance), and that they can be constructed efficiently, in a strong sense. Specifically, given the index of a vertex in such a graph, it is possible to find all its neighbors in polynomial-time (i.e., in time that is poly-logarithmic in the size of the graph). We also consider graphs of unbounded degree, seeking correspondingly unbounded robustness parameters. We again demonstrate that such graphs (of linear degree) exist (in abundance), and that they can be constructed efficiently, in a strong sense. This turns out to require very different tools. Specifically, we show that the construction of such graphs reduces to the construction of non-malleable two-source extractors (with very weak parameters but with some additional natural features). We demonstrate that robustly self-ordered bounded-degree graphs are useful towards obtaining lower bounds on the query complexity of testing graph properties both in the bounded-degree and the dense graph models. One of the results that we obtain, via such a reduction, is a subexponential separation between the query complexities of testing and tolerant testing of graph properties in the bounded-degree graph model.


    Volume: Volume 1
    Published on: December 21, 2022
    Accepted on: July 30, 2022
    Submitted on: December 2, 2021
    Keywords: Computer Science - Computational Complexity
    Funding:
      Source : OpenAIRE Graph
    • AF: Medium: Theory of Computation - New Algorithmic and Hardness Techniques; Funder: National Science Foundation; Code: 1900460
    • Foundations of Verifiable Computing; Funder: European Commission; Code: 819702

    Consultation statistics

    This page has been seen 517 times.
    This article's PDF has been downloaded 272 times.