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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the Sherali-Adams linear programming hierarchy in the context ofpromise constraint satisfaction problems (PCSPs). We characterise when a levelof the hierarchy accepts an instance in terms of a homomorphism problem for anappropriate multilinear structure obtained through a tensor power of theconstraint language. The geometry of this structure, which consists in a spaceof tensors satisfying certain symmetries, allows then to establishnon-solvability of the approximate graph colouring problem via constantly manylevels of Sherali-Adams.  Besides this primary application, our tensorisation construction introduces anew tool to the study of hierarchies of algorithmic relaxations forcomputational problems within (and, possibly, beyond) the context of constraintsatisfaction. In particular, we see it as a key step towards the algebraiccharacterisation of the power of Sherali-Adams for PCSPs.

The Sherali-Adams Hierarchy for Promise CSPs through Tensors