Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-154 | 28th August 2026 12:50

Feasible disjunction for random resolution

RSS-Feed




TR26-154
Authors: Theodoros Papamakarios
Publication: 28th August 2026 13:55
Downloads: 33
Keywords: 


Abstract:

We show that a (stronger) version of random resolution has the feasible disjunction property. This is the first instance of a proof system not known to have feasible interpolation, which nevertheless has the feasible disjunction property.



ISSN 1433-8092 | Imprint