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 of read--once ...
more >>>