11

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)

End Anti-Semitic Hate
  • 103
  • 1
  • 4
Shaull
  • 5,571
  • 1
  • 22
  • 32
  • 5
    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. https://arxiv.org/abs/1909.08065 – Chandra Chekuri Jan 03 '22 at 20:01
  • @ChandraChekuri - looks very interesting! I was mostly familiar with LLL in the context of the probabilistic method, not algorithms. Thanks. – Shaull Jan 03 '22 at 20:10
  • 2
    Related: https://cstheory.stackexchange.com/q/11425/129 – Joshua Grochow Jan 03 '22 at 20:22
  • 1
    If search problems fall in the ambit of the question then Perfect Matching Search is one problem that can be solved in (functional) RNC using the isolating lemma of Mulmuley, Vazirani and Vazirani but not known to be in NC. Also note that recent papers by Anari and Vazirani NC-reduce the search problem to the weighted decision problem (i.e. determine if there exists a perfect matching of weight at most W). This problem is, of course, amenable to the isolation lemma method but not known to be in NC. – SamiD Jan 04 '22 at 09:34
  • 3
    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. – Bruno Jan 04 '22 at 13:35
  • 3
    @Bruno GW algorithm and related ones have been derandomized via connections to small space algorithms for rounding. See the paper by Mahajan and Ramesh. https://epubs.siam.org/doi/pdf/10.1137/S0097539796309326 – Chandra Chekuri Jan 04 '22 at 14:16
  • @ChandraChekuri Thanks, I actually had known this but forgot it! – Bruno Jan 04 '22 at 15:43
  • (a) PRIMES used to be in this category. (b) "is there some fundamental barrier that prevents us from developing new tools" -- maybe it's the opposite: we are too good at developing tools that place problems in P, such that only a few known problems in BPP have yet to succumb. – usul Jan 04 '22 at 16:35
  • @usul - Indeed, this is the great derandomization task. But I wouldn't say we're "too good" until we resolve BPP vs P. – Shaull Jan 04 '22 at 18:35
  • 2
    related: https://cstheory.stackexchange.com/questions/31195/when-does-randomization-speed-up-algorithms-and-it-shouldnt/ – Neal Young Jan 05 '22 at 02:00
  • 1
    @ChandraChekuri: Regarding the LLL, the search problem is indeed in BPP (and not known to be in P in some cases), but I can't think of a language for which this holds. Am I missing something? – Or Sattath Jan 06 '22 at 22:08
  • 2
    @OrSattath, I interpreted the question somewhat liberally and just wanted to point an interesting setting where we are unable to derandomize an efficient randomized algorithm. I did not focus on decision problems specifically. Hopefully the OP found this still relevant. – Chandra Chekuri Jan 07 '22 at 02:53
  • @ChandraChekuri - It's certainly interesting. Even the fact that this sparked some discussion is interesting. I was worried that I'm just missing some well-studied field with many approaches. But the scarcity of approaches certainly means that any related technique is relevant. – Shaull Jan 07 '22 at 08:08

2 Answers2

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

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

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • 1
    Thanks! I'll wait a day to possibly attract more answers, before accepting. – Shaull Jan 03 '22 at 20:38
  • 3
    @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. – Joshua Grochow Jan 03 '22 at 21:38
  • sure thing. I'll wait a little longer. – Shaull Jan 04 '22 at 06:52
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) 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.

Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90
  • Interesting! Would you say Cantor-Zassenhaus has similarities to Schwartz-Zippel? (they certainly share a domain), or is it a fundamentally different idea? – Shaull Jan 04 '22 at 13:19
  • 2
    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. – Emil Jeřábek Jan 04 '22 at 13:41
  • Right. Cool, thanks. – Shaull Jan 04 '22 at 14:26
  • Related: https://sites.math.rutgers.edu/~sk1233/pit-factor.pdf – Markus Bläser Jan 19 '22 at 11:39
  • @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. – Emil Jeřábek Jan 19 '22 at 17:24