All Questions
Tagged with derandomization randomized-algorithms
19 questions
0
votes
0
answers
58
views
Does randomness help depth?
Suppose we have a $RNC^i$ or $BPNC^i$ algorithm for a problem, is it suspected that the problem has an $NC^i$ algorithm or just an $NC^j$ algorithm for some $j\geq i$?
Is there any evidence for ...
- 13.3k
11
votes
2
answers
893
views
Randomized algorithms not based on Schwartz-Zippel
Are there any problems that are known to be in a randomized complexity class (e.g. RNC, ZPP, RP, BPP, or even PP), but not in any lower non-randomized class (e.g. NC, P, NP), and whose membership in ...
- 5,636
3
votes
1
answer
468
views
Can the halting problem be solved probabilistically? [closed]
Let $H$ be the halting oracle, meaning that $H$ is a function on pairs of strings such that $H(P,X) = 1$ iff $P$ halts on $X$. A probabilistic program is a program that has (oracle) access to a random ...
- 134
1
vote
1
answer
126
views
Efficient randomness reduction using k-wise independence
Consider a randomized algorithm with runtime $n$, which succeeds with high probability. The algorithm uses $O(n)$ uniformly random bits.
Now it is given that we can replace these uniformly random ...
- 849
10
votes
1
answer
293
views
Uniform derandomisation of circuit complexity classes
Let $\mathcal{C}$ be a complexity class and $\textrm{BP-}\mathcal{C}$ be the randomized counterpart of $\mathcal{C}$ defined in the same way as $\textrm{BPP}$ is defined with respect to $\textrm{P}$. ...
- 1,002
14
votes
1
answer
471
views
Adleman's theorem over infinite semirings?
Adleman has shown in 1978 that $\mathrm{BPP}\subseteq \mathrm{P/poly}$: if a boolean function $f$ of $n$ variables can be computed by a probabilistic boolean circuit of size $M$, then $f$ can be also ...
- 6,795
16
votes
5
answers
2k
views
Examples of successful derandomization from BPP to P
What are some major examples of successful derandomization or at least progress in showing concrete evidence towards $P=BPP$ goal (not the hardness randomness connection)?
The only example that comes ...
user34945
5
votes
1
answer
360
views
Smallest $f(n)$ such that $P/f(n) = BPP/f(n)$?
It is well-known that $\mathsf{P/poly}(n) = \mathsf{BPP/poly}(n)$.
It is a major open problem to prove the conjecture $\mathsf{P} = \mathsf{BPP}$.
$\mathsf{P} = \mathsf{BPP}$ implies $\mathsf{P}/f(n) ...
- 663
-1
votes
1
answer
251
views
Is there a randomized complexity class analogous to $\mathsf{P/Poly}$?
$\mathsf{P/Poly}$ captures those problems that could be solved in polynomial time given some precomputed polynomial number of constants.
Is there an analogous complexity class in randomized world ...
- 13.3k
4
votes
0
answers
191
views
Randomized Parallel Algorithm for Maximal Independent Set
There are a couple of randomized parallel algorithms for the maximal independent set problem, e.g. A Simple Parallel Algorithm for the Maximal Independent Set Problem, A fast and simple randomized ...
- 1,338
4
votes
0
answers
164
views
Concentration Bounds for Dependent Rounding
Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$:
At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
- 271
7
votes
0
answers
638
views
Narrowing the gap between BPP and RP
We do not know yet whether the 2-sided error of $BPP$ allows more computing power than the one sided error of $RP$. In view of derandomization results, the conjectured answer is no, since both classes ...
- 11.4k
39
votes
9
answers
4k
views
Efficient and simple randomized algorithms where determinism is difficult
I often hear that for many problems we know very elegant randomized algorithms, but no, or only more complicated, deterministic solutions. However, I only know a few examples for this. Most ...
- 877
10
votes
1
answer
304
views
What are some results on algorithms that estimate polynomials over a given set of points?
There seem to be many randomized algorithms for polynomial identity testing, checking whether or not a given polynomial is zero. Are there any results of algorithms that do some sort of estimation of ...
- 109
18
votes
3
answers
839
views
Does randomness buy us anything inside P?
Let $\mathsf{BPTIME}(f(n))$ be the class of the decision problems having a bounded two-sided error randomized algorithm running in time $O(f(n))$.
Do we know of any problem $Q \in \mathsf{P}$ such ...
- 951
19
votes
3
answers
703
views
Running a BPP algorithm with a half-random, half-adversarial string
Consider the following model: an n-bit string r=r1...rn is chosen uniformly at random. Next, each index i∈{1,...,n} is put into a set A with independent probability 1/2. Finally, an adversary ...
- 13.9k
4
votes
1
answer
276
views
What's the strict definition of random coins in streaming algorithm?
I have a very basic question about random bits in streaming. How could a streaming algorithm use them? Can the algorithm use the same random bit at the start of the execution and look at it again ...
- 331
18
votes
2
answers
2k
views
Beginner's Guide to Derandomization
I found the book Pairwise Independence and Derandomization on the subject, but it's more research-oriented than tutorial oriented.
I'm new to the subject of "Derandomization," and as such, I wanted ...
- 16.6k
28
votes
4
answers
2k
views
What specific evidence is there for P = RP?
RP is the class of problems decidable by a nondeterministic Turing machine that terminates in polynomial time, but that is also allowed one-sided error. P is the usual class of problems decidable by ...
- 19.2k