9

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 ...


6

Suppose you had such a randomized procedure that takes a value in $\{-1,1\}$ and outputs a real number. Let $P$ and $Q$ be the output distribution on input $+1$ and $-1$ respectively. Consider the extreme case of $\mu = +1$. In this case $Y = +1$ for sure, and you are outputting a sample from $P$, which means that $P$ should be an $\mathcal{N}(\nu, 1)$ ...


6

It is well known that any language or function computable by a probabilistic algorithm is also computable deterministically. Here, we require that with probability $>1/2$, the algorithm outputs the correct answer (and therefore halts), but we allow the existence of infinite runs where the algorithm uses infinitely many random bits. Indeed, by $\sigma$-...


3

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 ...


2

There is this quasi-linear time approximation algorithm based on HyperLogLog: https://papers-gamma.link/paper/187


1

Today you should probably use Tabulation hashing for Linear Probing. In The Power of Simple Tabulation Hashing by Mihai Pătrașcu and Mikkel Thorup, this is shown to have at least the same guarantees as 5 independent hashing. Later work shows that it gives you better concentration (worst case bounds) as well. Tabulation hashing is also a lot faster than even ...


1

Though unrelated, this lecture note contains a potential function based neat proof of the $O(\log k)$-approximation.


1

The Perfect Matching problem was "almost" derandomized in 2016 [1]: there is a deterministic algorithm requiring "only" quaispolynomial resources, namely $n^{\mathcal O(\log n)}$ for the bipartite case and $n^{\mathcal O(\log^2n)}$ for the general case (in 2017 [2]). Although Edmonds gave a polynomial-time algorithm for perfect matching, ...


Only top voted, non community-wiki answers of a minimum length are eligible