### Abstract

It is shown that there exists a sequence of 3-regular graphs {G _{n}}^{∞}_{n=1} and a Hadamard space X such that {G_{n}}^{∞}_{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]. {G_{n}}^{∞}_{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 language | English (US) |
---|---|

Title of host publication | ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science |

Publisher | Association for Computing Machinery |

Pages | 353-358 |

Number of pages | 6 |

ISBN (Print) | 9781450322430 |

DOIs | |

State | Published - Jan 1 2014 |

Externally published | Yes |

Event | 2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014 - Princeton, NJ, United States Duration: Jan 12 2014 → Jan 14 2014 |

### Publication series

Name | ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science |
---|

### Other

Other | 2014 5th Conference on Innovations in Theoretical Computer Science, ITCS 2014 |
---|---|

Country | United States |

City | Princeton, NJ |

Period | 1/12/14 → 1/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

*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