10
$\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)

Improve this question
$\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$
    – Chandra Chekuri
    Jan 3 at 20:01
  • 2
    $\begingroup$ Related: cstheory.stackexchange.com/q/11425/129 $\endgroup$
    – Joshua Grochow
    Jan 3 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
    Jan 4 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$
    – Chandra Chekuri
    Jan 4 at 14:16
  • 2
    $\begingroup$ related: cstheory.stackexchange.com/questions/31195/… $\endgroup$
    – Neal Young
    Jan 5 at 2:00
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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks! I'll wait a day to possibly attract more answers, before accepting. $\endgroup$
    – Shaull
    Jan 3 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$
    – Joshua Grochow
    Jan 3 at 21:38
  • $\begingroup$ sure thing. I'll wait a little longer. $\endgroup$
    – Shaull
    Jan 4 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.

Improve this answer
$\endgroup$
3
  • $\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
    Jan 4 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$
    – Emil Jeřábek
    Jan 4 at 13:41
  • $\begingroup$ Right. Cool, thanks. $\endgroup$
    – Shaull
    Jan 4 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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