Towards a Characterization of Approximation Resistance for Symmetric CSPs

DOI10.4230/LIPICS.APPROX-RANDOM.2015.305zbMATH Open1375.68103OpenAlexW2285292888MaRDI QIDQ5351908FDOQ5351908

Venkatesan Guruswami, Euiwoong Lee

Publication date: 31 August 2017

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5309/pdf/19.pdf/

zbMATH Keywords

constraint satisfaction problemsapproximation resistance

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Cited In (2)

• A characterization of approximability for biased CSPs
• Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph

This page was built for publication: Towards a Characterization of Approximation Resistance for Symmetric CSPs

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