Sherali-Adams and the binary encoding of combinatorial principles

Dantchev, Stefan; Ghani, Abdul; Martin, Barnaby

doi:10.1007/978-3-030-61792-9_27

Sherali-Adams and the binary encoding of combinatorial principles

Dantchev, Stefan; Ghani, Abdul; Martin, Barnaby

Authors

Dr Stefan Dantchev s.s.dantchev@durham.ac.uk
Assistant Professor

Abdul Aziz Saud Abdul Ghani abdul.ghani@durham.ac.uk
PGR Student Doctor of Philosophy

Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor

Contributors

Yoshiharu Kohayakawa
Editor

Flávio Keidi Miyazawa
Editor

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). Sherali-Adams and the binary encoding of combinatorial principles. In Y. Kohayakawa, & F. K. Miyazawa (Eds.), LATIN 2020: Theoretical Informatics (336-347). https://doi.org/10.1007/978-3-030-61792-9_27

Conference Name	LATIN 2020
Conference Location	São Paulo, Brazil
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
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