Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ABDUL GHANI:
All reports by Author Abdul Ghani:

TR21-022 | 20th February 2021
Stefan Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin

Depth lower bounds in Stabbing Planes for combinatorial principles

Revisions: 1

We prove logarithmic depth lower bounds in Stabbing Planes for the classes of combinatorial principles known as the Pigeonhole principle and the Tseitin contradictions. The depth lower bounds are new, obtained by giving almost linear length lower bounds which do not depend on the bit-size of the inequalities and in ... more >>>




ISSN 1433-8092 | Imprint