Sherali-Adams Integrality Gaps Matching the Log-Density Threshold

Understand

The log-density method is a powerful algorithmic framework which in recent years has given rise to the best-known approximations for a variety of problems, including Densest-$k$-Subgraph and Bipartite Small Set Vertex Expansion.

• These approximations have been conjectured to be optimal based on various instantiations of a general conjecture: that it is hard to distinguish a fully random combinatorial structure from one which contains a similar planted sub-structure with the same "log-density".
• We bolster this conjecture by showing that in a random hypergraph with edge probability $n^{-\alpha}$, $\tilde\Omega(\log n)$ rounds of Sherali-Adams with cannot rule out the existence of a $k$-subhypergraph with edge density $k^{-\alpha-o(1)}$, for any $k$ and $\alpha$.
• This holds even when the bound on the objective function is lifted.