Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Florian Wörz:

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 >>>

TR21-097 | 7th July 2021
Jacobo Toran, Florian Wörz

Number of Variables for Graph Identification and the Resolution of GI Formulas

We show that the number of variables and the quantifier depth needed to distinguish a pair of graphs by first-order logic sentences exactly match the complexity measures of clause width and positive depth needed to refute the corresponding graph isomorphism formula in propositional narrow resolution.

Using this connection, we ... more >>>

TR19-097 | 4th July 2019
Jacobo Toran, Florian Wörz

Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space

Revisions: 1 , Comments: 1

We show a new connection between the space measure in tree-like resolution and the reversible pebble game in graphs. Using this connection we provide several formula classes for which there is a logarithmic factor separation between the space complexity measure in tree-like and general resolution. We show that these separations ... more >>>

ISSN 1433-8092 | Imprint