On semantic cutting planes with very small coefficients

0489225 - MÚ 2019 RIV NL eng J - Journal Article
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
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : theory of computation * proof complexity * cutting planes
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 0.914, year: 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.
Permanent Link: http://hdl.handle.net/11104/0283676