Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > NIKITA GAEVOY:
All reports by Author Nikita Gaevoy:

TR25-160 | 24th October 2025
Yaroslav Alekseev, Nikita Gaevoy

Intersection Theorems: A Potential Approach to Proof Complexity Lower Bounds

Recently, Göös et al. (2024) showed that Res ? uSA = RevRes in the following sense: if a formula $\varphi$ has refutations of size at most $s$ and width/degree at most $w$ in both Res and uSA, then there is a refutation for $\varphi$ of size at most $poly(s·2^w)$ in ... more >>>




ISSN 1433-8092 | Imprint