### Abstract

We prove that there is a universal constant C > 0 with the following property. Suppose that n ∈ ℕ and that A = (a_{ij}) ∈ M_{n}(ℝ) is a symmetric stochastic matrix. Denote the second-largest eigenvalue of A by λ_{2}(A). Then for any finite-dimensional normed space (X, ⊥ · ⊥) we have (Equation presented) It follows that if an n-vertex O(1)-expander embeds with average distortion D ≧ 1 into X, then necessarily dim(X) ≳ n^{c}/^{D} for some universal constant c > 0. This is sharp up to the value of the constant c, and it improves over the previously best-known estimate dim(X) ≳ (log n)^{2}/D^{2} of Linial, London and Rabinovich, strengthens a theorem of Matoušek, and answers a question of Andoni, Nikolov, Razenshteyn and Waingarten.

Original language | English (US) |
---|---|

Title of host publication | 33rd International Symposium on Computational Geometry, SoCG 2017 |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Pages | 501-5016 |

Number of pages | 4516 |

Volume | 77 |

ISBN (Electronic) | 9783959770385 |

DOIs | |

State | Published - Jun 1 2017 |

Event | 33rd International Symposium on Computational Geometry, SoCG 2017 - Brisbane, Australia Duration: Jul 4 2017 → Jul 7 2017 |

### Other

Other | 33rd International Symposium on Computational Geometry, SoCG 2017 |
---|---|

Country | Australia |

City | Brisbane |

Period | 7/4/17 → 7/7/17 |

### All Science Journal Classification (ASJC) codes

- Software

## Cite this

*33rd International Symposium on Computational Geometry, SoCG 2017*(Vol. 77, pp. 501-5016). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SoCG.2017.50