Definable Inapproximability: New Challenges for Duplicator

DOI10.4230/LIPIcs.CSL.2018.7OpenAlexW2963512679MaRDI QIDQ5079727

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)

Related Items (1)

Constructing Hard Examples for Graph Isomorphism

Cites Work

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

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