1
vote
4answers
99 views

What is an example for an algorithm which makes use the power of randomness?

Can someone give a (most simple) example for an algorithm on a machine, which has access to random numbers, and which is faster than any other known algorithm for the same task? My actual motivation ...
2
votes
2answers
103 views

Solovay Randomness

Say that an $x\in 2^{\omega}$ is Solovay random if for all computably enumerable collections of intervals $\{I_n\}$ such that $\sum_n\mu(I_n)<\infty$, then $x\in I_n$ for at most finitely many $n$. ...
1
vote
1answer
80 views

Finding a subsequence (of a very long sequence) which does not sum to an even number

[Edited. I've revised to problem to focus on the special case of the integers modulo 2.] You are given a function f from binary strings x ∈ {0,1}n to the integers, or (without loss of ...
3
votes
1answer
145 views

Can $BPP \subset P/poly$ be strengthened to a single infinitely long advice?

It is well known that $BPP \subset P/poly$, by probabilistic method. Can this be strengthened: Is there a single string $a \in \{0,1\}^{\omega}$ such that there's a polynomial time deterministic ...