TY - GEN
T1 - Towards a study of low-complexity graphs
AU - Arora, Sanjeev
AU - Steurer, David
AU - Wigderson, Avi
N1 - Funding Information:
Supported by NSF grants 0830673, 0832797, 528414.
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=70449086300&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70449086300&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-02927-1_12
DO - 10.1007/978-3-642-02927-1_12
M3 - Conference contribution
AN - SCOPUS:70449086300
SN - 3642029264
SN - 9783642029264
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 119
EP - 131
BT - Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Proceedings
T2 - 36th International Colloquium on Automata, Languages and Programming, ICALP 2009
Y2 - 5 July 2009 through 12 July 2009
ER -