Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Weisfeiler--Leman Algorithm:
TR23-063 | 2nd May 2023
Jacobo Toran, Florian Wörz

Cutting Planes Width and the Complexity of Graph Isomorphism Refutations

The width complexity measure plays a central role in Resolution and other propositional proof systems like Polynomial Calculus (under the name of degree). The study of width lower bounds is the most extended method for proving size lower bounds, and it is known that for these systems, proofs with small ... more >>>

ISSN 1433-8092 | Imprint