Non-deterministic branching programs with logarithmic repetition cannot efficiently compute small monotone CNFs

Oded Lachish, Igor Razgon

In this paper we establish an exponential lower bound on the size of syntactic non-deterministic read $d$-times branching programs for $d\le \log n/10^5$ computing a class of mo…