Approximate distance oracles
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
- Localized and compact data-structure for comparability graphs
- A data structure for bicategories, with application to speeding up an approximation algorithm
- Thorup-Zwick emulators are universally optimal hopsets
- New pairwise spanners
- On efficient distributed construction of near optimal routing schemes
- Impact of knowledge on election time in anonymous networks
- NP-hardness and fixed-parameter tractability of the minimum spanner problem
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- An introduction to the Ribe program
- Ultrametric subsets with large Hausdorff dimension
- Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
- Distance estimation and object location via rings of neighbors
- Preprocess, set, query!
- A fast algorithm for source-wise round-trip spanners
- Advice complexity of treasure hunt in geometric terrains
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Multiple-edge-fault-tolerant approximate shortest-path trees
- Constructing light spanners deterministically in near-linear time
- Light spanners for high dimensional norms via stochastic decompositions
- An axiomatic approach to time-dependent shortest path oracles
- Byzantine gathering in polynomial time
- Routing among convex polygonal obstacles in the plane
- Minimum \(t\)-spanners on subcubic graphs
- On random perfect matchings in metric spaces with not-too-large diameters
- Routing in polygonal domains
- Near-optimal induced universal graphs for cycles and paths
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Exact and approximation algorithms for weighted matroid intersection
- Fault tolerant additive and \((\mu, \alpha)\)-spanners
- Deterministic improved round-trip spanners
- Distributed distance computation and routing with small messages
- Additive spanners and distance and routing labeling schemes for hyperbolic graphs
- Faster algorithms for all-pairs small stretch distances in weighted graphs
- Topology recognition with advice
- Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- Colouring and covering nowhere dense graphs
- Approximate distance oracles with improved bounds
- The Power of Dynamic Distance Oracles
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Clustered Integer 3SUM via Additive Combinatorics
- Matching triangles and basing hardness on an extremely popular conjecture
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Proof of the satisfiability conjecture for large k
- On the complexity of random satisfiability problems with planted solutions (extended abstract)
- Sum-of-squares Lower Bounds for Planted Clique
- Sum of squares lower bounds from pairwise independence (extended abstract)
- Inapproximability of combinatorial problems via small LPs and SDPs
- Preserving statistical validity in adaptive data analysis (extended abstract)
- Local, private, efficient protocols for succinct histograms
- Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions
- Dictionary learning and tensor decomposition via the sum-of-squares method
- Randomized composable core-sets for distributed submodular maximization
- Dimensionality reduction for k-means clustering and low rank approximation
- Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
- _p row sampling by Lewis weights
- On the Lovász theta function for independent sets in sparse graphs
- The complexity of the simplex method
- An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
- Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
- Nearly-linear time positive LP solver with faster convergence rate
- Spectral sparsification and regret minimization beyond matrix multiplicative updates
- Almost Optimal Pseudorandom Generators for Spherical Caps
- Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition
- The List Decoding Radius of Reed-Muller Codes over Small Fields
- A characterization of the capacity of online (causal) binary channels
- Reed-Muller codes for random erasures and errors
- Forrelation: a problem that optimally separates quantum from classical computing
- Quantum information complexity
- Sparse quantum codes from quantum circuits
- Small value parallel repetition for general games
- An interactive information odometer and applications
- The communication complexity of interleaved group products
- Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory's theorem
- Approximating the Nash social welfare with indivisible items
- On the complexity of Nash equilibria in anonymous games
- Hardness of Graph Pricing Through Generalized Max-Dicut
- Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
- Inapproximability of Nash equilibrium
- Indistinguishability obfuscation for Turing machines with unbounded memory
- Succinct garbling and indistinguishability obfuscation for RAM programs
- Succinct randomized encodings and their applications
- Garbled RAM from one-way functions
- Non-malleable reductions and applications
- Leveled fully homomorphic signatures from standard lattices
- Sketching and embedding are equivalent for norms
- A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds
- Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
- Bypassing KLS: Gaussian cooling and an O^(n^3) volume algorithm
- FPTAS for \#BIS with degree bounds on one side
- Lower bounds on the size of semidefinite programming relaxations
- Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract)
- High Parallel Complexity Graphs and Memory-Hard Functions
- Byzantine agreement with optimal early stopping, optimal resilience and polynomial complexity
- Test-and-set in optimal space
- Adjacency labeling schemes and induced-universal graphs
- How well can graphs represent wireless interference?
- Excluded grid theorem: improved and simplified
- The directed grid theorem
This page was built for publication: Approximate distance oracles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546311)
