[Proof Complexity] a new preprint

[Jan Krajicek]

  Dear colleagues,

  a preliminary version of my paper

   "Randomized feasible interpolation and monotone
    circuits with a local oracle"

is available at

  http://www.karlin.mff.cuni.cz/~krajicek/biblio.html#posledni

It ought to be available also at the ArXiv from the 29th.
Abstract is below. Comments are most welcome.

                            Regards,

                                   Jan

Abstract:

  We generalize the feasible interpolation theorem for semantic derivations
from K.(1997) by allowing randomized protocols (protocols in the sense of
K.(1997). We also introduce an extension of the monotone circuit model,
monotone circuits with a local oracle (CLOs), that does correspond to
communication protocols for the monotone Karchmer-Wigderson multi-function
$KW^m[U,V]$ making errors. The new randomized feasible interpolation thus shows
that a short semantic derivation (from a certain class of derivations larger
than in the original method) of the disjointness of $U, V$, $U$ closed upwards,
yields a small randomized protocol for and hence a small monotone CLO
separating the sets. To establish a lower bound for monotone CLOs separating
two NP sets, one closed upwards, is an open problem.

   This research is motivated by the open problem to establish a lower bound for
proof system $R(LIN)$ operating with clauses formed by linear Boolean functions
over the 2-element field. The new randomized feasible interpolation applies to
this proof system and also to the semantic versions of the cutting planes proof
system (as randomized protocols efficiently simulate protocols with small real
communication complexity of K.(1998)) and to random resolution of Buss,
Kolodziejczyk and Thapen (2014).The lower bound for the tree-like subsystem of
$R(LIN)$ was proved by Itsykson and Sokolov (2014).