There is a quadratic randomized algorithm for matrix product verification.
Is there a similar trick to 'verify given three integers $n,a,b$ if $n=ab$ holds?' in $O(\log n)$ time?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Should be $O(\log n)$ or else it would be exponential time. $\endgroup$ – 1.. Jan 26 at 22:38
-
$\begingroup$ I am a bit surprised by the downvotes. This question appears very natural to me, and my impression is that Kaminski's result (cf my answer) is not very well-known. $\endgroup$ – Bruno Feb 8 at 15:21
Add a comment
|
$\begingroup$
$\endgroup$
6
There is a linear time randomized algorithm, that is of complexity $O(\log n)$: Cf M. Kaminski, A note on probabilistically verifying integer and polynomial products, J. ACM 36(1), pp. 142–149, Jan. 1989.
The basic idea: Instead of checking $n = ab$ modulo $p$ for some random prime number $p$, check it modulo $2^i-1$ for some integer $i$. The reduction modulo $2^i-1$ is fast (faster than modulo a prime $p$) since only additions are required. And if you take $i = O(\log^{1-\epsilon} n)$, the computation of $(a\bmod 2^i-1)(b\bmod 2^i-1)$ can be done in (sub)linear time. Kaminski proves that if $n\neq ab$, $n\not\equiv ab\bmod 2^i-1$ with high probability.
-
$\begingroup$ It still seems we require $(\log n)(f(n))$ at an $f(n)\in\omega(1)$ (might be at any $f(n)\in\omega(1)$) to achieve $1-o(1)$ probability of success. So to achieve $1-o(1)$ error there is no $O(\log n)$ complexity algorithm? $\endgroup$ – 1.. Feb 9 at 12:05
-
-
2$\begingroup$ No, Kaminski's algorithm has a probability of failure $1/n^{O(1)}$, not a constant probability. What is not yet known is whether there exists a deterministic linear-time algorithm. $\endgroup$ – Bruno Feb 10 at 11:05
-
$\begingroup$ Probability of success of $1-\frac{\mathsf{polylog}(n)}{n}$ on a single trial is deterministic $O(\log n)$. But if it were even $1-\frac{2^{\mathsf{polyloglog(n)}}}{n}$ it would not be. So it depends on what $O(1)$ is. If error $\geq\frac{1}{n^{O(1)}}$ means error $\geq\frac{2^{\mathsf{polyloglog}(n)}}{n}$ we would require $\omega(\log n)$ randomized trials. So randomized in $O(\log n)$ would itself be unsolved. $\endgroup$ – 1.. Feb 10 at 12:20
-
3$\begingroup$ I cannot make any sense of what you write. If this is the question, no we don't know any $O(\log n)$ algorithm with error probability smaller than $1/n^{O(1)}$, for instance error $1/2^n$. $\endgroup$ – Bruno Feb 10 at 13:44
$\begingroup$
$\endgroup$
5
Yes. One algorithm is: pick a random $k$-bit prime $p$; reduce $n,a,b$ modulo $p$, and then check whether $n \equiv ab \pmod p$. The chance of failing to detect an error is exponentially small in $k$, and the running time is something like $O(k \log n)$ (can probably be reduced to something like $O((\log k)(\log n))$ in theory by using efficient multiplication/division algorithms).
-
$\begingroup$ @EmilJeřábek, you're right, I got confused. Thank you. $\endgroup$ – D.W. Jan 26 at 22:20
-
$\begingroup$ So to get to $o(1)$ probability of certifying inequality it needs $\Omega(\log\log n)$ trials? $\endgroup$ – 1.. Jan 26 at 23:52
-
$\begingroup$ @1.. No. First, $k$ needs to be at least about $\log\log n$ so that the probability of error is $<1$ in the first place. But after that, the probability is $O(2^{-k}\log n)$, thus $k=\log\log n+O(1)$ is enough to get the probability down to, say, $1/2$, in which case $\omega(1)$ trials will make the probability $o(1)$; and if $k=\log\log n+\omega(1)$, a single trial will already give probability $o(1)$. $\endgroup$ – Emil Jeřábek Jan 27 at 15:31
-
1$\begingroup$ By the way, it is simpler to do the test modulo arbitrary random $k$-bit numbers rather than just primes. Then one doesn’t have to bother with primality testing, rejection sampling, etc. Again, $k$ needs to be above roughly $\log\log n$, and then the error is something like $\rho(k/\log\log n)$, where $\rho$ is the Dickman function. In particular, $k\sim c\log\log n$ for a constant $c>1$ will give error probability bounded away from $1$, and $k=\omega(\log\log n)$ will give $o(1)$. $\endgroup$ – Emil Jeřábek Jan 27 at 15:37
-
$\begingroup$ Is there a similar complexity derandomization? What is the best derandomization we know? Randomized time complexity is $O((\log n)(\log\log\log n)f(n))$ at any $f(n)\in\omega(1)$ which is faster compared to complexity of integer multiplication. $\endgroup$ – 1.. Jan 27 at 17:04
