Sherali-Adams and the binary encoding of combinatorial principles
(2020)
Conference Proceeding
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
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 r... Read More about Sherali-Adams and the binary encoding of combinatorial principles.