Document Open Access Logo

Definable Inapproximability: New Challenges for Duplicator

Authors Albert Atserias , Anuj Dawar

PDF
Thumbnail PDF

File

LIPIcs.CSL.2018.7.pdf
  • Filesize: 0.54 MB
  • 21 pages

Document Identifiers

Author Details

Albert Atserias
  • Departament de Ciències de la Computació, Universitat Politècnica de Catalunya, Barcelona, Catalonia, Spain
Anuj Dawar
  • Department of Computer Science and Technology, University of Cambridge, UK

Funding

  • Atserias, Albert: Partially funded by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement ERC-2014-CoG 648276 (AUTAR) and MICCIN grant TIN2016-76573-C2-1P (TASSAT3).
  • Dawar, Anuj: Supported in part by a Fellowship of the Alan Turing Institute.

Cite AsGet BibTex

Albert Atserias and Anuj Dawar. Definable Inapproximability: New Challenges for Duplicator. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.CSL.2018.7

Abstract

We consider the hardness of approximation of optimization problems from the point of view of definability. For many NP-hard optimization problems it is known that, unless P = NP, no polynomial-time algorithm can give an approximate solution guaranteed to be within a fixed constant factor of the optimum. We show, in several such instances and without any complexity theoretic assumption, that no algorithm that is expressible in fixed-point logic with counting (FPC) can compute an approximate solution. Since important algorithmic techniques for approximation algorithms (such as linear or semidefinite programming) are expressible in FPC, this yields lower bounds on what can be achieved by such methods. The results are established by showing lower bounds on the number of variables required in first-order logic with counting to separate instances with a high optimum from those with a low optimum for fixed-size instances.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
  • Theory of computation → Finite Model Theory
Keywords
  • Descriptive Compleixty
  • Hardness of Approximation
  • MAX SAT
  • Vertex Cover
  • Fixed-point logic with counting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. S. Abramsky, A. Dawar, and P. Wang. The pebbling comonad in finite model theory. In Proc. of the 32nd IEEE Symp. on Logic in Computer Science (LICS)., 2017. Google Scholar
  2. M. Anderson, A. Dawar, and B. Holm. Solving linear programs without breaking abstractions. J. ACM, 62, 2015. Google Scholar
  3. S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Google Scholar
  4. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, 1998. Google Scholar
  5. A. Atserias. On sufficient conditions for unsatisfiability of random formulas. J. ACM, 51:281-311, 2004. Google Scholar
  6. A. Atserias, A. Bulatov, and A. Dawar. Affine systems of equations and counting infinitary logic. Theoretical Computer Science, 410(18):1666-1683, 2009. Google Scholar
  7. A. Atserias and V. Dalmau. A combinatorial characterization of resolution width. J. Comput. Syst. Sci., 74:323-334, 2008. Google Scholar
  8. A. Atserias and A. Dawar. Definable inapproximability: New challenges for duplicator. arXiv, 2018. URL: http://arxiv.org/abs/1806.11307.
  9. A. Atserias and J. Ochremiak. Definable ellipsoid method, sums-of-squares proofs, and the isomorphism problem. arxiv 1802.02388. Google Scholar
  10. E. Ben-Sasson and A. Wigderson. Short proofs are narrow - resolution made simple. J. ACM, 48:149-169, 2001. Google Scholar
  11. A. Dawar. The nature and power of fixed-point logic with counting. ACM SIGLOG News, pages 8-21, 2015. Google Scholar
  12. A. Dawar and P. Wang. A definability dichotomy for finite valued CSPs. In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015, pages 60-77, 2015. Google Scholar
  13. A. Dawar and P. Wang. Definability of semidefinite programming and lasserre lower bounds for CSPs. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, 2017. URL: http://dx.doi.org/10.1109/LICS.2017.8005108.
  14. I. Dinur and S. Safra. On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162:439–485, 2005. Google Scholar
  15. Martin Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, volume 47 of Lecture Notes in Logic. Cambridge University Press, 2017. Google Scholar
  16. J. Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. Google Scholar
  17. Lauri Hella. Logical hierarchies in PTIME. Information and Computation, 129(1):1-19, 1996. Google Scholar
  18. T. Holenstein. Parallel repetition: Simplifications and the no-signaling case. In Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, STOC '07, pages 411-419, New York, NY, USA, 2007. ACM. URL: http://dx.doi.org/10.1145/1250790.1250852.
  19. N. Immerman and E. S. Lander. Describing graphs: A first-order approach to graph canonization. In A. Selman, editor, Complexity Theory Retrospective. Springer-Verlag, 1990. Google Scholar
  20. S. Khot, D. Minzer, and M. Safra. Pseudorandom sets in grassmann graph have near-perfect expansion. Technical Report TR18-006, Electronic Colloquium on Computational Complexity (ECCC), 2018. Google Scholar
  21. Phokion G Kolaitis and Moshe Y Vardi. On the expressive power of Datalog: Tools and a case study. In Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 61-71. ACM, 1990. Google Scholar
  22. Ch. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. Google Scholar
  23. Ch. H. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43(3):425-440, 1991. Google Scholar
  24. R. Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763-803, 1998. Google Scholar
  25. G. Schoenebeck. Linear level lasserre lower bounds for certain k-CSPs. In Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 593-602, 2008. Google Scholar
  26. S. Vadhan. Pseudorandomness, volume 7:1-3 of Foundations and Trends in Theoretical Computer Science. Now Foundations and Trends, December 2012. Google Scholar
  27. V. V. Vazirani. Approximation Algorithms. Springer, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact