English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We study the approximability of constraint satisfaction problems (CSPs) bylinear programming (LP) relaxations. We show that for every CSP, theapproximation obtained by a basic LP relaxation, is no weaker than theapproximation obtained using relaxations given by $\Omega\left(\frac{\logn}{\log \log n}\right)$ levels of the Sherali-Adams hierarchy on instances ofsize $n$.  It was proved by Chan et al. [FOCS 2013] that any polynomial size LP extendedformulation is no stronger than relaxations obtained by a super-constant levelsof the Sherali-Adams hierarchy.. Combining this with our result also impliesthat any polynomial size LP extended formulation is no stronger than the basicLP.  Using our techniques, we also simplify and strengthen the result by Khot etal. [STOC 2014] on (strong) approximation resistance for LPs. They provided anecessary and sufficient condition under which $\Omega(\log \log n)$ levels ofthe Sherali-Adams hierarchy cannot achieve an approximation better than arandom assignment. We simplify their proof and strengthen the bound to$\Omega\left(\frac{\log n}{\log \log n}\right)$ levels.

From Weak to Strong LP Gaps for all CSPs