11
$\begingroup$

Are there any problems that are known to be in a randomized complexity class (e.g. RNC, ZPP, RP, BPP, or even PP), but not in any lower non-randomized class (e.g. NC, P, NP), and whose membership in the randomized class is not based on the Schwartz-Zippel lemma?

If not, is there some fundamental barrier that prevents us from developing new tools? (apart from the obvious fact that we don't know whether randomization helps)

$\endgroup$
13
  • 5
    $\begingroup$ Another general technique is via Lovasz-Local-Lemma. Not all applications have been derandomized. I am no expert in this area but thought the recent paper by Harris is useful to look at. arxiv.org/abs/1909.08065 $\endgroup$ Commented Jan 3, 2022 at 20:01
  • 2
    $\begingroup$ Related: cstheory.stackexchange.com/q/11425/129 $\endgroup$ Commented Jan 3, 2022 at 20:22
  • 3
    $\begingroup$ Aren't there examples in the field of approximation algorithm? For instance, Goemans-Williamson randomized algorithm provides a cut in a graph that is at least 0.878 of the optimal cut and I do not think one knows how to derandomize it. I have not thought whether one can define a decision problem around this question that would be in BPP using GW algorithm but not known to be in P. $\endgroup$
    – Bruno
    Commented Jan 4, 2022 at 13:35
  • 3
    $\begingroup$ @Bruno GW algorithm and related ones have been derandomized via connections to small space algorithms for rounding. See the paper by Mahajan and Ramesh. epubs.siam.org/doi/pdf/10.1137/S0097539796309326 $\endgroup$ Commented Jan 4, 2022 at 14:16
  • 2
    $\begingroup$ related: cstheory.stackexchange.com/questions/31195/… $\endgroup$
    – Neal Young
    Commented Jan 5, 2022 at 2:00

2 Answers 2

8
$\begingroup$

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 this problem is in $\mathsf{BPP}$.

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

$\endgroup$
3
  • 1
    $\begingroup$ Thanks! I'll wait a day to possibly attract more answers, before accepting. $\endgroup$
    – Shaull
    Commented Jan 3, 2022 at 20:38
  • 3
    $\begingroup$ @Shaull: Thanks. While this seems like a perfectly good answer, I'm also happy for you to wait longer than that. I'd be curious to see what else shows up. I think it's a very interesting question, as there are lots of techniques for randomized algorithms, but not so many techniques for putting something into e.g. RP that we didn't already know was in P. $\endgroup$ Commented Jan 3, 2022 at 21:38
  • $\begingroup$ sure thing. I'll wait a little longer. $\endgroup$
    – Shaull
    Commented Jan 4, 2022 at 6:52
7
$\begingroup$

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) decision problem by suitably normalizing the result to make it unique (e.g., require all the irreducible factors to be monic and sorted in lexicographic order), and then taking the bit-graph. This will be a ZPP problem not known to be in P.

$\endgroup$
5
  • $\begingroup$ Interesting! Would you say Cantor-Zassenhaus has similarities to Schwartz-Zippel? (they certainly share a domain), or is it a fundamentally different idea? $\endgroup$
    – Shaull
    Commented Jan 4, 2022 at 13:19
  • 2
    $\begingroup$ I don’t see a direct connection. If you just look at the special case of quadratic polynomials, Schwartz–Zippel is based on the fact that a univariate quadratic polynomial has at most 2 roots (hence with high probability, a random element is a nonroot), whereas Cantor–Zassenhaus is based on the fact that half of elements of a finite field are quadratic residues (hence with probability 1/2, a random shift of the polynomial has a nontrivial gcd with $x^{(p-1)/2}\pm1$). These seem to be rather different properties to me. $\endgroup$ Commented Jan 4, 2022 at 13:41
  • $\begingroup$ Right. Cool, thanks. $\endgroup$
    – Shaull
    Commented Jan 4, 2022 at 14:26
  • $\begingroup$ Related: sites.math.rutgers.edu/~sk1233/pit-factor.pdf $\endgroup$ Commented Jan 19, 2022 at 11:39
  • $\begingroup$ @MarkusBläser Interesting. But note that this is a different set-up: on the one hand, they deal with factorization of multivariate polynomials rather than univariate; on the other hand, for finite fields, they allow running time polynomial in $p$ rather than $\log p$. In fact, they note on p. 4 that derandomization of univariate polynomial factoring in time polynomial in $\log p$ is the main stumbling block that they couldn’t reduce to PIT. $\endgroup$ Commented Jan 19, 2022 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.