A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds
From MaRDI portal
Publication:2941543
DOI10.1145/2746539.2746595zbMath1321.68210arXiv1404.1191OpenAlexW2010820875MaRDI QIDQ2941543
Suresh Venkatasubramanian, Amirali Abdullah
Publication date: 21 August 2015
Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1404.1191
Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)
Related Items
Hypercontractivity for global functions and sharp thresholds, Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems
Uses Software
Cites Work
- Unnamed Item
- Ramsey partitions and proximity data structures
- On sparse spanners of weighted graphs
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- On Approximate Distance Labels and Routing Schemes with Affine Stretch
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Approximate distance oracles
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Shortest-path queries in static networks
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
