@inproceedings{39c410cff41f499cba257a5e2cb7ae6d,
title = "Expanders with respect to hadamard spaces and random graphs",
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.",
keywords = "CAT(0), Euclidean cone, Expanders, Hadamard spaces, Metric embeddings, Random regular graphs",
author = "Manor Mendel and Assaf Naor",
year = "2014",
doi = "10.1145/2554797.2554829",
language = "אנגלית",
isbn = "9781450322430",
series = "ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science",
publisher = "Association for Computing Machinery",
pages = "353--358",
booktitle = "ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science",
note = "2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014 ; Conference date: 12-01-2014 Through 14-01-2014",
}