Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs.

Ludmila Glinskih, Dmitry Itsykson

Browse the full MFCS paper archive.