Expanders with respect to hadamard spaces and random graphs

Manor Mendel, Assaf Naor

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

Abstract

It is shown that there exists a sequence of 3-regular graphs {G n}n=1 and a Hadamard space X such that {Gn}n=1 forms an expander sequence with respect to X, yet random regular graphs are not expanders with respect to X. This answers a question of [31]. {Gn}n=1 are also shown to be expanders with respect to random regular graphs, yielding a deterministic sublinear time constant factor approximation algorithm for computing the average squared distance in subsets of a random graph. The proof uses the Euclidean cone over a random graph, an auxiliary continuous geometric object that allows for the implementation of martingale methods. This extended abstract does not contain proofs. The full version of this paper can be found at arXiv: 1306.5434.

Original languageEnglish (US)
Title of host publicationITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science
PublisherAssociation for Computing Machinery
Pages353-358
Number of pages6
ISBN (Print)9781450322430
DOIs
StatePublished - Jan 1 2014
Externally publishedYes
Event2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014 - Princeton, NJ, United States
Duration: Jan 12 2014Jan 14 2014

Publication series

NameITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science

Other

Other2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014
CountryUnited States
CityPrinceton, NJ
Period1/12/141/14/14

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics

Keywords

  • CAT(0)
  • Euclidean cone
  • Expanders
  • Hadamard spaces
  • Metric embeddings
  • Random regular graphs

Fingerprint Dive into the research topics of 'Expanders with respect to hadamard spaces and random graphs'. Together they form a unique fingerprint.

  • Cite this

    Mendel, M., & Naor, A. (2014). Expanders with respect to hadamard spaces and random graphs. In ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science (pp. 353-358). (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science). Association for Computing Machinery. https://doi.org/10.1145/2554797.2554829