On semantic cutting planes with very small coefficients

0489225 - MÚ 2019 RIV NL eng J - Článek v odborném periodiku
Lauria, M. - Thapen, Neil
On semantic cutting planes with very small coefficients.
Information Processing Letters. Roč. 136, August (2018), s. 70-75. ISSN 0020-0190. E-ISSN 1872-6119
Grant CEP: GA ČR GBP202/12/G061
Institucionální podpora: RVO:67985840
Klíčová slova: theory of computation * proof complexity * cutting planes
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impakt faktor: 0.914, rok: 2018
https://www.sciencedirect.com/science/article/pii/S0020019018300875

Cutting planes proofs for integer programs can naturally be defined both in a syntactic and in a semantic fashion. Filmus et al. (STACS 2016) proved that semantic cutting planes proofs may be exponentially stronger than syntactic ones, even if they use the semantic rule only once. We show that when semantic cutting planes proofs are restricted to have coefficients bounded by a function growing slowly enough, syntactic cutting planes can simulate them efficiently. Furthermore if we strengthen the restriction to a constant bound, then the simulating syntactic proof even has polynomially small coefficients.
Trvalý link: http://hdl.handle.net/11104/0283676