Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > REAL COMMUNICATION COMPLEXITY:
Reports tagged with real communication complexity:
TR17-151 | 8th October 2017
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

Stabbing Planes

Revisions: 3

We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by
branching on an inequality and its "integer negation.'' That is, we can (nondeterministically ... more >>>




ISSN 1433-8092 | Imprint