An Algorithmic Blend of LPs and Ring Equations for Promise CSPs

DOI10.1137/1.9781611975482.28zbMath1431.68043arXiv1807.05194OpenAlexW2884037933MaRDI QIDQ5236209

Joshua Brakensiek, Venkatesan Guruswami

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.05194

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Linear programming (90C05) Applications of universal algebra in computer science (08A70)

Related Items (8)

CLAP: A New Algorithm for Promise CSPs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems ⋮ Sandwiches for promise constraint satisfaction ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})

This page was built for publication: An Algorithmic Blend of LPs and Ring Equations for Promise CSPs