<p>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 <a href="https://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm" rel="noreferrer">Cantor–Zassenhaus algorithm</a>, but no deterministic (FP) algorithm is known (this is open even for the special case of computing square roots modulo primes).</p>
<p>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.</p>

CC BY-SA 4.0
2022-01-04T13:19:46.757Z
Interesting! Would you say Cantor-Zassenhaus has similarities to Schwartz-Zippel? (they certainly share a domain), or is it a fundamentally different idea?
Shaull
CC BY-SA 4.0
2022-01-04T13:41:02.920Z
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
CC BY-SA 4.0
2022-01-04T14:26:43.047Z
Right. Cool, thanks.
Shaull
CC BY-SA 4.0
2022-01-19T11:39:13.953Z
Related: https://sites.math.rutgers.edu/~sk1233/pit-factor.pdf
Markus Bläser
CC BY-SA 4.0
2022-01-19T17:24:30.337Z
@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
CC BY-SA 4.0
2022-01-04T12:48:27.527Z
2022-01-04T13:05:43.107Z
2022-01-04T13:05:43.107Z
Emil Jeřábek
<p><a href="https://cstheory.stackexchange.com/a/11440/129">Here</a> is a natural problem known to be in <span class="math-container">$\mathsf{BPP}$</span> but not <span class="math-container">$\mathsf{RP} \cup \mathsf{coRP}$</span>, Problem 2.6 of [1]: Given a prime <span class="math-container">$p$</span>, integers <span class="math-container">$N$</span> and <span class="math-container">$d$</span>, and a list <span class="math-container">$A$</span> of invertible <span class="math-container">$d \times d$</span> matrices over <span class="math-container">$\mathbb{F}_{p}$</span>, does the group generated by <span class="math-container">$A$</span> have a quotient of order <span class="math-container">$\geq N$</span> with no abelian normal subgroups? In [1] it is shown that this problem is in <span class="math-container">$\mathsf{BPP}$</span>.</p>
<p>[1] L. Babai, R. Beals, A. Seress. <a href="http://dx.doi.org/10.1145/1536414.1536425" rel="noreferrer">Polynomial-time theory of matrix groups</a>. STOC 2009.</p>

CC BY-SA 4.0
2022-01-03T20:38:59.747Z
Thanks! I'll wait a day to possibly attract more answers, before accepting.
Shaull
CC BY-SA 4.0
2022-01-03T21:38:37.880Z
@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
CC BY-SA 4.0
2022-01-04T06:52:07.987Z
sure thing. I'll wait a little longer.
Shaull
CC BY-SA 4.0
2022-01-03T20:21:38.337Z
2022-01-03T20:21:38.337Z
Joshua Grochow
<p>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 <strong>not</strong> based on the Schwartz-Zippel lemma?</p>
<p>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)</p>

CC BY-SA 4.0
2022-01-03T20:01:21.927Z
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
CC BY-SA 4.0
2022-01-03T20:10:21.410Z
@ChandraChekuri - looks very interesting! I was mostly familiar with LLL in the context of the probabilistic method, not algorithms. Thanks.
Shaull
CC BY-SA 4.0
2022-01-03T20:22:11.193Z
Related: https://cstheory.stackexchange.com/q/11425/129
Joshua Grochow
CC BY-SA 4.0
2022-01-04T09:34:12.447Z
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
CC BY-SA 4.0
2022-01-04T13:35:30.997Z
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
CC BY-SA 4.0
2022-01-04T14:16:16.670Z
@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
CC BY-SA 4.0
2022-01-04T15:43:59.553Z
@ChandraChekuri Thanks, I actually had known this but forgot it!
Bruno
CC BY-SA 4.0
2022-01-04T16:35:58.837Z
(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
CC BY-SA 4.0
2022-01-04T18:35:02.133Z
@usul - Indeed, this is the great derandomization task. But I wouldn't say we're "too good" until we resolve BPP vs P.
Shaull
CC BY-SA 4.0
2022-01-05T02:00:50.583Z
related: https://cstheory.stackexchange.com/questions/31195/when-does-randomization-speed-up-algorithms-and-it-shouldnt/
Neal Young
CC BY-SA 4.0
2022-01-06T22:08:41.160Z
@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
CC BY-SA 4.0
2022-01-07T02:53:53.720Z
@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
CC BY-SA 4.0
2022-01-07T08:08:02.607Z
@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
<cc.complexity-theory><randomized-algorithms><derandomization>
Randomized algorithms not based on Schwartz-Zippel
Shaull
# Randomized algorithms not based on Schwartz-Zippel

(Asked by: username_0 on 2022-01-03)

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)

**Tags:** cc.complexity-theory, randomized-algorithms, derandomization
> **Comments:**
> **username_1**: 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  
> **username_0**: @ChandraChekuri - looks very interesting! I was mostly familiar with LLL in the context of the probabilistic method, not algorithms. Thanks.  
> **username_2**: Related: https://cstheory.stackexchange.com/q/11425/129  
> **username_3**: 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.  
> **username_4**: 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.  
> **username_1**: @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  
> **username_4**: @ChandraChekuri Thanks, I actually had known this but forgot it!  
> **username_5**: (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.  
> **username_0**: @usul - Indeed, this is the great derandomization task. But I wouldn't say we're "too good" until we resolve BPP vs P.  
> **username_6**: related: https://cstheory.stackexchange.com/questions/31195/when-does-randomization-speed-up-algorithms-and-it-shouldnt/  
> **username_7**: @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?  
> **username_1**: @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.  
> **username_0**: @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.  

---

## 2 answers

### Answer by username_2 on 2022-01-03. Score: 8 | Accepted answer

[Here](https://cstheory.stackexchange.com/a/11440/129) 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](http://dx.doi.org/10.1145/1536414.1536425). STOC 2009.

> **Comments:**
> **username_0**: Thanks! I'll wait a day to possibly attract more answers, before accepting.  
> **username_2**: @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.  
> **username_0**: sure thing. I'll wait a little longer.  

---

### Answer by username_8 on 2022-01-04. Score: 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](https://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_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.

> **Comments:**
> **username_0**: Interesting! Would you say Cantor-Zassenhaus has similarities to Schwartz-Zippel? (they certainly share a domain), or is it a fundamentally different idea?  
> **username_8**: 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.  
> **username_0**: Right. Cool, thanks.  
> **username_9**: Related: https://sites.math.rutgers.edu/~sk1233/pit-factor.pdf  
> **username_8**: @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.  

---

