Bypassing KLS

DOI10.1145/2746539.2746563zbMath1321.68434arXiv1409.6011OpenAlexW2025334959MaRDI QIDQ2941546

Benjamin R. Cousins, Santosh Vempala

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

zbMATH Keywords

samplingfunctional analysisvolume computationgeometric random walks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)

Related Items (13)

Randomly coloring simple hypergraphs with fewer colors ⋮ Practical Volume Estimation of Zonotopes by a New Annealing Schedule for Cooling Convex Bodies ⋮ A practical volume algorithm ⋮ Efficient sampling in spectrahedra and volume approximation ⋮ Sampling from a log-concave distribution with projected Langevin Monte Carlo ⋮ Total variation discrepancy of deterministic random walks for ergodic Markov chains ⋮ Error regions in quantum state tomography: computational complexity caused by geometry of quantum states ⋮ Convergence of Gibbs sampling: coordinate hit-and-run mixes fast ⋮ Systematics of aligned axions ⋮ An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths ⋮ Normalizing constants of log-concave densities ⋮ An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution ⋮ An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes

Uses Software

• Graphs
• Volume

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: Bypassing KLS