3 problems

0 votes0 replies0 views
Goemans–Linial conjecture on the integrality gap for Sparsest Cut
Goemans–Linial conjecture. The integrality gap satisfies
Conjectureopenmetric-embeddings semidefinite-programming sparsest-cutarXiv posted 2 days ago
0 votes0 replies2 views
Steurer's conjecture on separated sets of nearly orthogonal vectors
Let $obreakforall obreaktext{?}$ For every $obreaktext{?}$
Conjectureopenhigh-dimensional-expanders sparsest-cut sum-of-squaresarXiv posted 2 days ago
0 votes0 replies0 views
Removal of the lower-order factor in the general-demand Sparsest Cut approximation
Let $C,D:\{1,\ldots,n\}\times\{1,\ldots,n\}\to[0,\infty)$ be symmetric capacity and demand functions, and let $M^{**}(C,D)$ and $\Phi^*(C,D)$ denote the semidefinite relaxation and…
Conjectureopenapproximation-algorithms semidefinite-programming sparsest-cutarXiv posted 2 days ago

Goemans–Linial conjecture on the integrality gap for Sparsest Cut