Sherali-Adams and the binary encoding of combinatorial principles

Dantchev, Stefan; Ghani, Abdul; Martin, Barnaby

Abstract

We consider the Sherali-Adams ( SA ) refutation system together with the unusual binary encoding of certain combinatorial principles. For the unary encoding of the Pigeonhole Principle and the Least Number Principle, it is known that linear rank is required for refutations in SA , although both admit refutations of polynomial size. We prove that the binary encoding of the Pigeonhole Principle requires exponentially-sized SA refutations, whereas the binary encoding of the Least Number Principle admits logarithmic rank, polynomially-sized SA refutations. We continue by considering a refutation system between SA and Lasserre (Sum-of-Squares). In this system, the unary encoding of the Least Number Principle requires linear rank while the unary encoding of the Pigeonhole Principle becomes constant rank.

Citation

Dantchev, S., Ghani, A., & Martin, B. (2020, May). Sherali-Adams and the binary encoding of combinatorial principles. Presented at LATIN 2020, São Paulo, Brazil

• Presentation Conference Type: Conference Paper (published)
• Conference Name: LATIN 2020
• Start Date: May 25, 2020
• End Date: May 29, 2020
• Acceptance Date: Feb 10, 2020
• Online Publication Date: Dec 3, 2020
• Publication Date: 2020
• Deposit Date: Jun 29, 2020
• Publicly Available Date: Jun 30, 2020
• Print ISSN: 0302-9743
• Publisher: Springer Verlag
• Volume: 12118
• Pages: 336-347
• Series Title: Lecture Notes in Computer Science
• Book Title: LATIN 2020: Theoretical Informatics
• ISBN: 9783030617912
• DOI: https://doi.org/10.1007/978-3-030-61792-9_27
• Public URL: https://durham-repository.worktribe.com/output/1140499
• Related Public URLs: https://arxiv.org/abs/1911.00403