[Proof Complexity] A note on semantic vs syntactic cutting planes

[Massimo Lauria]

Dear colleagues,

I just uploaded on my webpage a note about semantic/syntactic cutting planes by
by Yuval Filmus and myself.

Please let us know your comments, observations, questions or followup results.

Best,

TITLE: A separation between semantic and syntactic cutting planes

ABSTRACT:
In this note we argue that semantic cutting planes refutations are
stronger than syntactic ones. In particular, we give a formula for
which any refutation in syntactic cutting planes requires exponential
length, while there is a polynomial length refutation in semantic
cutting planes. This means that syntactic cutting planes does not
p-simulate (nor simulate) semantic cutting planes.
We  also give  a pair  of  incompatible cutting  planes lines  which
require exponential length to be  refuted in syntactic cutting planes.


LINK:
On my webpage (see "manuscript" section)
http://www.csc.kth.se/~lauria/writings.html

A direct link
http://www.csc.kth.se/~lauria/documents/semantic-cp.pdf
-- 
Massimo Lauria
KTH Royal Institute of Technology
School of Computer Science and Communication
Osquars Backe 2, SE-100 44 Stockholm, Sweden
+46 (0) 73 8008 125 (Cell.)
httlp://www.csc.kth.se/~lauria/