Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs
Stephen A Cook, Jeff A. Edmonds, Venkatesh Medabalimi, Toniann Pitassi · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
We prove exponential lower bounds on the size of semantic read-once 3-ary nondeterministic branching programs. Prior to our result the best that was known was for D-ary branching programs with |D| >= 2^{13}.