Definable inapproximability: new challenges for duplicator

DOI10.1093/logcom/exz022zbMath1446.68072arXiv1806.11307OpenAlexW2996910805WikidataQ127239977 ScholiaQ127239977MaRDI QIDQ5216336

Anuj Dawar, Albert Atserias

Publication date: 17 February 2020

Published in: Journal of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1806.11307

zbMATH Keywords

vertex coverhardness of approximationdescriptive complexityMAX SATfixed-point logic with counting

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)

Related Items (1)

On the Weisfeiler-Leman dimension of fractional packing

This page was built for publication: Definable inapproximability: new challenges for duplicator