@inproceedings { ,
title = {Sherali-Adams and the binary encoding of combinatorial principles},
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.},
conference = {LATIN 2020},
doi = {10.1007/978-3-030-61792-9\_27},
isbn = {9783030617912},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {336-347},
publicationstatus = {Published},
publisher = {Springer Verlag},
url = {https://durham-repository.worktribe.com/output/1140499},
volume = {12118},
keyword = {Algorithms and Complexity in Durham (ACiD)},
year = {2024},
author = {Dantchev, Stefan and Ghani, Abdul and Martin, Barnaby}
editor = {Kohayakawa, Yoshiharu and Miyazawa, Flávio Keidi}
}