New answers tagged probabilistic-algorithms
1
vote
Accepted
What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?
I think there must be some confusion in the problem setting. Given an input of $n$ bits chosen uniformly at random, there is no algorithm to compress it to something whose length is on average ...
D.W.♦
- 156k
1
vote
How many random bits does this algorithm use on average?
I don't have a formal proof, but I expect the expected value is $\lg n + O(1)$ bits. In particular, heuristically I am expecting something like $\lg n + 2.9$ bits or so (but I don't trust that the ...
D.W.♦
- 156k
Top 50 recent answers are included