Towards a study of low-complexity graphs

Sanjeev Arora, David Steurer, Avi Wigderson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings
Pages119-131
Number of pages13
EditionPART 1
DOIs
StatePublished - Nov 12 2009
Event36th International Colloquium on Automata, Languages and Programming, ICALP 2009 - Rhodes, Greece
Duration: Jul 5 2009Jul 12 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume5555 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other36th International Colloquium on Automata, Languages and Programming, ICALP 2009
CountryGreece
CityRhodes
Period7/5/097/12/09

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Towards a study of low-complexity graphs'. Together they form a unique fingerprint.

  • Cite this

    Arora, S., Steurer, D., & Wigderson, A. (2009). Towards a study of low-complexity graphs. In Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings (PART 1 ed., pp. 119-131). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5555 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-02927-1_12