We prove logarithmic depth lower bounds in Stabbing Planes for the classes ofcombinatorial principles known as the Pigeonhole principle and the Tseitincontradictions . Depth lower bounds are new, obtained by giving almostlinear length lower bounds which do not depend on the bit-size of the .inequalities . The technique known so far to prove depth lower . bounds is a generalization of that used for the Cutting Planes proof system . In this work we introduce two new approaches to prove length/depth lower bounds . One relying on Sperner’s Theorem which works for the Pigonholeprinciple and Tseitsin contradictions over the complete graph . A second proving
Author(s) : Stefan Dantchev, Nicola Galesi, Abdul Ghani, Barnaby MartinLinks : PDF - Abstract
Code :
Keywords : bounds - depth - planes - prove - stabbing -