Definable Inapproximability: New Challenges for Duplicator

DOI10.4230/LIPICS.CSL.2018.7OpenAlexW2963512679MaRDI QIDQ5079727FDOQ5079727

Albert Atserias, Anuj Dawar

Publication date: 28 May 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9674/pdf/LIPIcs-CSL-2018-7.pdf/

zbMATH Keywords

vertex coverhardness of approximationmax SATfixed-point logic with countingdescriptive compleixty

Mathematics Subject Classification ID

Logic in computer science (03B70)

Cites Work

• Optimization, approximation, and complexity classes
• Title not available (Why is that?)
• Computational Complexity
• Proof verification and the hardness of approximation problems
• Some optimal inapproximability results
• On the hardness of approximating minimum vertex cover
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Parallel Repetition Theorem
• Short proofs are narrow—resolution made simple
• Affine systems of equations and counting infinitary logic
• Logical hierarchies in PTIME
• A combinatorial characterization of resolution width
• Title not available (Why is that?)
• On sufficient conditions for unsatisfiability of random formulas
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• A Definability Dichotomy for Finite Valued CSPs
• Solving Linear Programs without Breaking Abstractions
• Title not available (Why is that?)
• Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem

Cited In (2)

• Constructing Hard Examples for Graph Isomorphism
• Definable inapproximability: new challenges for duplicator

This page was built for publication: Definable Inapproximability: New Challenges for Duplicator

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