Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > FLORIAN WÖRZ:
All reports by Author Florian Wörz:

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