New answers tagged randomized-algorithms
7
This is a search problem rather than a decision problem: factorization of polynomials over finite fields can be done in randomized polynomial time (TFZPP) using the Cantor–Zassenhaus algorithm, but no deterministic (FP) algorithm is known (this is open even for the special case of computing square roots modulo primes).
You can turn it into a (less natural) ...
8
Here is a natural problem known to be in $\mathsf{BPP}$ but not $\mathsf{RP} \cup \mathsf{coRP}$, 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 ...
4
The deterministic communication complexity of the problem is $\Theta(n\log{n})$: it is sufficient to show the existance of a family $S$ of partitions such that $|S|= 2^{\Omega(n\log{n})}$ and that for any $P_1,P_2 \in S$, $P_1$ refines $P_2$ iff $P_1 = P_2$, as this is a fooling set that implies a bound of $\Omega(n\log{n})$. Let $S$ be the set of partitions ...
Top 50 recent answers are included