A (log n)^(Ω(1)) integrality gap for the Sparsest Cut SDP
read the original abstract
We show that the Goemans-Linial semidefinite relaxation of the Sparsest Cut problem with general demands has integrality gap $(\log n)^{\Omega(1)}$. This is achieved by exhibiting $n$-point metric spaces of negative type whose $L_1$ distortion is $(\log n)^{\Omega(1)}$. Our result is based on quantitative bounds on the rate of degeneration of Lipschitz maps from the Heisenberg group to $L_1$ when restricted to cosets of the center.
This paper has not been read by Pith yet.
Forward citations
Cited by 4 Pith papers
-
PCCL: Process Group-Aware Scalable and Generic Collective Algorithm Synthesizer
PCCL synthesizes near-optimal topology-aware collective algorithms for arbitrary patterns while being process group-aware and scalable to subsets of devices.
-
Performance Isolation and Semantic Determinism in Efficient GPU Spatial Sharing
CoGPU resolves the tradeoff in GPU sharing by introducing GPU coroutines for semantic-preserving resource migration, delivering up to 79.2% higher training throughput and zero token mismatch in inference.
-
SigmaScale: LLM Compression with SVD-based Low-Rank Decomposition and Learned Scaling Matrices
Learned diagonal scaling matrices optimized with activation-aware loss reduce effective rank in LLM weight matrices and yield competitive perplexity and zero-shot results versus prior SVD methods on Llama 3.1 8B and Qwen3-8B.
-
FlexPipe: Adapting Dynamic LLM Serving Through Inflight Pipeline Refactoring in Fragmented Serverless Clusters
FlexPipe introduces runtime pipeline refactoring for LLMs to achieve higher resource efficiency and lower latency in serverless GPU clusters with fragmentation.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.