From Independence to Expansion and Back Again

DOI10.1145/2746539.2746620zbMath1321.68219arXiv1506.03676OpenAlexW2009316475MaRDI QIDQ2941578

Tobias Christiani, Rasmus Pagh, Mikkel Thorup

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/1506.03676

zbMATH Keywords

\(k\)-independencehash functionsbipartite expanders

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (3)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence ⋮ A combinatorial approach to quantum random functions

Uses Software

• Graphs

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

This page was built for publication: From Independence to Expansion and Back Again