Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > YASSINE GHANNANE:
All reports by Author Yassine Ghannane:

TR26-078 | 3rd May 2026
Susanna F. de Rezende, David Engström, Yassine Ghannane, Kilian Risse

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size

We prove superpolynomial length lower bounds for the semantic tree-like Frege refutation system with bounded line size. Concretely, for any function $n^{2-\varepsilon} \leq s(n) \leq \exp\bigl(n^{1-\varepsilon}\bigr)$ we exhibit an explicit family $\mathcal{A}$ of $n$-variate CNF formulas $A$, each of size $|A| \le s(n)^{1+\varepsilon}$, such that if $A$ is chosen uniformly ... more >>>




ISSN 1433-8092 | Imprint