Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > LEA KASCHE:
All reports by Author Lea Kasche:

TR26-219 | 28th September 2026
Olaf Beyersdorff, Lea Kasche, Luc Nicolas Spachmann

Fine-Grained Size-Cost-Capacity for Strong Semantic QBF Proof Systems

We revisit the semantic size-cost-capacity technique (Beyersdorff, Blinkhorn & Hinde, 2019) for proof-size lower bounds in proof systems for quantified Boolean formulas (QBF). While the original technique is only applicable to weak proof systems with bounded capacity, we present a fine-grained generalisation of this technique that allows us to attack ... more >>>




ISSN 1433-8092 | Imprint