<p>I think <a href="https://en.wikipedia.org/wiki/Polynomial_identity_testing" rel="nofollow noreferrer">Polynomial identity testing</a> fits the question. If you have the right encoding for polynomials, you can test the equality by evaluating the polynomials on random values in linear time over <span class="math-container">$\mathbb{Z}/p\mathbb{Z}$</span> for a random large <span class="math-container">$p$</span>. We don't know how to do that in polynomial time without randomness (and therefore the result is stronger than just linear time).</p>

CC BY-SA 4.0
2024-10-14T22:49:30.510Z
Yes I should have been clear on this, is there anything else more similar to element distinctness?  Actually I don't think you need any specific encoding, since as you say it is not known to be in P (so even if I consider polynomials in $n^{0.1}$ variables it's still not clear how to do it in linear time).  I updated the question.
Manu
CC BY-SA 4.0
2024-10-15T08:41:55.663Z
Second proposition: [Freivalds' algorithm](https://en.wikipedia.org/wiki/Freivalds%27_algorithm). The complexity is $O(n^2)$  but here the input is $O(n^2)$ so it is actually linear.
Louis
CC BY-SA 4.0
2024-10-15T15:50:54.743Z
Freivalds' algorithm fits my bill so I'll accept this answer.
Manu
CC BY-SA 4.0
2024-10-17T20:06:04.587Z
Note that Freivalds algorithm is just PIT on quadratic polynomials. You can also consider a problem like: given a circuit of size n and degree n in one variable, is it identically zero? Now it's a quadratic time problem deterministically. Getting subquadratic time without randomness refutes the Non-deterministic SETH.
Ryan Williams
CC BY-SA 4.0
2024-10-18T12:47:21.313Z
Yes, but the formulation with matrices is cleaner and doesn't need finite fields etc.  Can you give me a pointer to this problem you are mentioning and the connection to SETH?  Also, I was hoping that element distinctness was such an example, but there's an annoying issue whether the input is given in bits or words; I don't see it gives such a separation for bits.
Manu
CC BY-SA 4.0
2024-10-14T05:25:01.413Z
2024-10-14T15:44:22.563Z
2024-10-14T15:44:22.563Z
Louis
<p>Is there a problem on <span class="math-container">$n$</span> bits that can be solved in linear time on a RAM with randomness, but we don't know how to solve in linear time without randomness?</p>
<p>Exclude polynomial-identity testing (see Louis' answer below).  I'm looking for something basic, perhaps similar to element distinctness.</p>
<p>The RAM model I'm interested in has <span class="math-container">$\log n$</span>-bit registers.  I can allow for a little more, but not <span class="math-container">$c \log n$</span>.  Equivalently, I allow for <span class="math-container">$c \log n$</span>-bit registers but I insist that the memory used is linear.</p>
<p>I don't think element distinctness qualifies.  It would if I allowed for <span class="math-container">$n$</span> cells as input, but not sure with bits.  Though maybe there's a variant that does qualify.</p>

CC BY-SA 4.0
2024-10-10T18:31:34.027Z
Can you be more specific about what you would accept for "solved"?  E.g. do you mean a decision problem?  Does the answer have to be correct (and the expected running time linear)?  Or does the answer only have to be correct with high (or greater than 2/3) probability?  Etc.  You mention linear time.  Do you intend to preclude padded problems (e.g., if there is a problem with a quadratic-time randomized algorithm but no known quadratic-time deterministic algorithm, you could artificially pad the inputs to turn the problem into one with a linear-time randomized alg...)?
Neal Young
CC BY-SA 4.0
2024-10-10T22:36:18.607Z
I was hoping decision problem, and "simple" like element distinctness or something like that, and say error probability 1/3.
Manu
CC BY-SA 4.0
2024-10-11T16:37:37.383Z
I'm confused by "insist that the memory used is linear".  Given that you are asking about linear-time algorithms, wouldn't they generally use at most linear space?
Neal Young
CC BY-SA 4.0
2024-10-11T17:00:47.383Z
Related: https://cstheory.stackexchange.com/q/11738/8237 (one of the answers mentions that there is a *sub*-linear time algorithm for approximating the value of a two-player zero-sum game in a certain way, but no such deterministic algorithm).  An easier example in this spirit is, given an array of $n$ 0/1 values, to estimate the number of entries that are ones, with, say, multiplicative error at most 0.01, with probability at least 2/3.
Neal Young
CC BY-SA 4.0
2024-10-14T22:44:11.707Z
With clog n-bit registers you can index memory location $n^2$, say.  The estimation problem doesn't work because it can be solved in linear deterministic time.  (It shows a different type of separation that I'm asking.)
Manu
<lower-bounds><randomness>
Randomness in RAM
Manu
# Randomness in RAM

(Asked by: username_0 on 2024-10-09)

Is there a problem on $n$ bits that can be solved in linear time on a RAM with randomness, but we don't know how to solve in linear time without randomness?

Exclude polynomial-identity testing (see username_2' answer below). I'm looking for something basic, perhaps similar to element distinctness.

The RAM model I'm interested in has $\log n$-bit registers. I can allow for a little more, but not $c \log n$. Equivalently, I allow for $c \log n$-bit registers but I insist that the memory used is linear.

I don't think element distinctness qualifies. It would if I allowed for $n$ cells as input, but not sure with bits. Though maybe there's a variant that does qualify.

**Tags:** lower-bounds, randomness

> **Comments:**
> **username_1**: Can you be more specific about what you would accept for "solved"?  E.g. do you mean a decision problem?  Does the answer have to be correct (and the expected running time linear)?  Or does the answer only have to be correct with high (or greater than 2/3) probability?  Etc.  You mention linear time.  Do you intend to preclude padded problems (e.g., if there is a problem with a quadratic-time randomized algorithm but no known quadratic-time deterministic algorithm, you could artificially pad the inputs to turn the problem into one with a linear-time randomized alg...)?  
> **username_0**: I was hoping decision problem, and "simple" like element distinctness or something like that, and say error probability 1/3.  
> **username_1**: I'm confused by "insist that the memory used is linear".  Given that you are asking about linear-time algorithms, wouldn't they generally use at most linear space?  
> **username_1**: Related: https://cstheory.stackexchange.com/q/11738/8237 (one of the answers mentions that there is a *sub*-linear time algorithm for approximating the value of a two-player zero-sum game in a certain way, but no such deterministic algorithm).  An easier example in this spirit is, given an array of $n$ 0/1 values, to estimate the number of entries that are ones, with, say, multiplicative error at most 0.01, with probability at least 2/3.  
> **username_0**: With clog n-bit registers you can index memory location $n^2$, say.  The estimation problem doesn't work because it can be solved in linear deterministic time.  (It shows a different type of separation that I'm asking.)  

---

## 1 answers

### Answer by username_2 on 2024-10-14. Score: 3 | Accepted answer

I think [Polynomial identity testing](https://en.wikipedia.org/wiki/Polynomial_identity_testing) fits the question. If you have the right encoding for polynomials, you can test the equality by evaluating the polynomials on random values in linear time over $\mathbb{Z}/p\mathbb{Z}$ for a random large $p$. We don't know how to do that in polynomial time without randomness (and therefore the result is stronger than just linear time).

> **Comments:**
> **username_0**: Yes I should have been clear on this, is there anything else more similar to element distinctness?  Actually I don't think you need any specific encoding, since as you say it is not known to be in P (so even if I consider polynomials in $n^{0.1}$ variables it's still not clear how to do it in linear time).  I updated the question.  
> **username_2**: Second proposition: [Freivalds' algorithm](https://en.wikipedia.org/wiki/Freivalds%27_algorithm). The complexity is $O(n^2)$  but here the input is $O(n^2)$ so it is actually linear.  
> **username_0**: Freivalds' algorithm fits my bill so I'll accept this answer.  
> **username_3**: Note that Freivalds algorithm is just PIT on quadratic polynomials. You can also consider a problem like: given a circuit of size n and degree n in one variable, is it identically zero? Now it's a quadratic time problem deterministically. Getting subquadratic time without randomness refutes the Non-deterministic SETH.  
> **username_0**: Yes, but the formulation with matrices is cleaner and doesn't need finite fields etc.  Can you give me a pointer to this problem you are mentioning and the connection to SETH?  Also, I was hoping that element distinctness was such an example, but there's an annoying issue whether the input is given in bits or words; I don't see it gives such a separation for bits.  

---

