Correlation decay and tractability of CSPs

DOI10.4230/LIPICS.ICALP.2016.79MaRDI QIDQ4598219zbMATH OpenOpenAlexFDO

Authors Jonah Brown-Cohen, Prasad Raghavendra

Publication date 19 December 2017

Full work available at URL https://dblp.uni-trier.de/db/conf/icalp/icalp2016.html#Brown-CohenR16

zbMATH Keywords

constraint satisfactioncorrelation decaylinear equationspolymorphisms

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• A proof of the CSP dichotomy conjecture
• Asking the Metaquestions in Constraint Tractability
• A new line of attack on the dichotomy conjecture
• A new line of attack on the dichotomy conjecture
• An algorithmic blend of LPs and ring equations for promise CSPs

Cited in

(6)

• On the classification of NP-complete problems in terms of their correlation coefficient
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• The Complexity of Problems in P Given Correlated Instances
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• The complexity of valued CSPs
• The complexity of general-valued CSPs

This page was built for publication: Correlation decay and tractability of CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598219)