Definable Inapproximability: New Challenges for Duplicator

DOI10.4230/LIPICS.CSL.2018.7MaRDI QIDQ5079727zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Definable inapproximability: new challenges for duplicator
• Inapproximability of unique games in fixed-point logic with counting
• Approximation properties of NP minimization classes
• The inapproximability of non-NP-hard optimization problems.

Cites work

• scientific article; zbMATH DE number 5485476 (Why is no real title available?)
• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• A Parallel Repetition Theorem
• A combinatorial characterization of resolution width
• A definability dichotomy for finite valued CSPs
• Affine systems of equations and counting infinitary logic
• Computational Complexity
• Definability of semidefinite programming and Lasserre lower bounds for CSPs
• Definable ellipsoid method, sums-of-squares proofs, and the isomorphism problem
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• Logical hierarchies in PTIME
• On sufficient conditions for unsatisfiability of random formulas
• On the hardness of approximating minimum vertex cover
• Optimization, approximation, and complexity classes
• Proof verification and the hardness of approximation problems
• Short proofs are narrow—resolution made simple
• Solving linear programs without breaking abstractions
• Some optimal inapproximability results
• The pebbling comonad in finite model theory

Cited in

(3)

• Inapproximability of unique games in fixed-point logic with counting
• 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)