Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Towards a Study of Low-Complexity Graphs
verfasst von : Sanjeev Arora, David Steurer, Avi Wigderson
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose the study of graphs that are defined by low-complexity distributed and deterministic agents. We suggest that this viewpoint may help introduce the element of
individual choice
in models of large scale social networks. This viewpoint may also provide interesting new classes of graphs for which to design algorithms.
We focus largely on the case where the “low complexity” computation is
AC
0
. We show that this is already a rich class of graphs that includes examples of lossless expanders and power-law graphs. We give evidence that even such low complexity graphs present a formidable challenge to algorithms designers. On the positive side, we show that many algorithms from property testing and data sketching can be adapted to give meaningful results for low-complexity graphs.