Majorizing Measures for the Optimizer
summary
Proves a constructive version of the majorizing measures duality: a convex program for the Gaussian chaining functional and a simplified dual are within a factor-two (up to additive diameter terms), and rounding those solutions yields explicit chaining and packing trees. Uses convex duality and rounding on metric spaces, yields deterministic polynomial-time algorithms to produce near-optimal trees (rounding in near-linear time given pairwise distances), works for general symmetric log-concave processes, and gives constructive Gordon-type projections and cover-time computations.
AI-written summary · about