Random resolution, defined by Buss, Kolodziejczyk and Thapen (JSL, 2014), is#N#a sound propositional proof system that extends the resolution proof system by#N#the possibility to augment any set of initial clauses by a set of randomly#N#chosen clauses (modulo a technical condition). We show how to apply the general#N#feasible interpolation theorem for semantic derivations of Krajicek (JSL, 1997)#N#to random resolution. As a consequence we get a lower bound for random#N#resolution refutations of the clique-coloring formulas.
['Jan Krajíček']
A feasible interpolation for random resolution