Problem in BPP but not known to be in RP or co-RP

Question

Is there an example of a natural problem that's in BPP but that's not known to be in RP or co-RP?

Answer 1

Moved my comment here after Suresh's request.

An example of a natural problem for which we only know algorithms that require error on both sides is the following: given three algebraic circuits, decide whether exactly two of them are identical. This comes from the fact that deciding whether two algebraic circuits are identical is in co-RP.

Reference: see the post How Many Sides to Your Error? (Dec 2, 2008) about the very same question on Lance Fortnow's blog and the comments below his post for a discussion about the naturalness of the problem.

Answer 2

An arguably more natural problem - not designed specifically for the purpose of finding a problem that might be in $\mathsf{BPP} \backslash \mathsf{RP} \cup \mathsf{coRP}$, and also not so closely related to a problem known to be in $\mathsf{coRP}$ - is furnished by Problem 2.6 of [1]: Given a prime $p$, integers $N$ and $d$, and a list $A$ of invertible $d \times d$ matrices over $\mathbb{F}_{p}$, does the group generated by $A$ have a quotient of order $\geq N$ with no abelian normal subgroups? In [1] it is shown that this problem is in $\mathsf{BPP}$.

While asking for quotients with no abelian normal subgroups might seem eccentric, the class of groups with no abelian normal subgroups (sometimes called semisimple) is actually fairly natural from the point of view of the structure theory of groups. See [2] and references therein.

[1] L. Babai, R. Beals, A. Seress. Polynomial-time theory of matrix groups. STOC 2009.

[2] L. Babai, P. Codenotti, Y. Qiao. Polynomial-time isomorphism test for groups with no abelian normal subgroups. To appear, ICALP 2012.