SBP is a probabilistic promise class located
between MA and AM \cap BPPpath. The first
part of the paper studies the question of whether
SBP has many-one complete sets. We relate
this question to the existence of uniform
enumerations. We construct an oracle relative to
which SBP and AM do ... more >>>

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 >>>

An arithmetic formula is multi-linear if the polynomial computed
by each of its sub-formulas is multi-linear. We prove that any
multi-linear arithmetic formula for the permanent or the
determinant of an $n \times n$ matrix is of size super-polynomial
in $n$.

more >>>