We prove the first lower bound for restricted read-once parity branching
programs with unlimited parity nondeterminism where for each input the
variables may be tested according to several orderings.

Proving a superpolynomial lower bound for read-once parity branching
programs is still a challenging open problem. The following variant ... more >>>