Questions tagged [probabilistic-algorithms]
Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.
226 questions
0
votes
1
answer
61
views
Bounded probabilistic log-space which halts with probability $1$
It is known that BPL $\subseteq$ P where BPL is the class of languages that have a probabilistic Turing machine which decides input correctly with probability $\ge \frac{2}{3}$ and always halts ...
- 3,413
1
vote
1
answer
86
views
Randomised Algorithm for Maximum Matching
Consider the following randomised distributed algorithm for computing (constant-approximation) maximum matching. The algorithm
has $\log ∆$ iterations indexed by $i∈{0,1,2,\ldots,\log ∆−
1}$. We ...
- 21
0
votes
0
answers
76
views
What is the expected number of layers in a skip list?
Skip lists work in layers. My question is no more than that: What is the expected number of layers in a skip list with the parameter $p \in (0,1)$? My best attempt to so far is
$$\sum_{i = 1}^\infty i ...
- 60
1
vote
0
answers
59
views
Why is this probability $o(1)$ as $m \to \infty$ in a proof of a randomized algorithm for solving $k$-CNF ($k$-SAT) ? A mistake in a famous book?
This is about the proof of Lemma 5.13 in the well-renowned book Motwani R, Raghavan P. Randomized Algorithms. Cambridge University Press; 1995. Access with institutional login: link.
(The lemma is in ...
- 11
5
votes
1
answer
219
views
Basic question about parallel repetition in IP protocol
The book Arora and Barak defines class IP (interactive protocol) by making the verifier have private coins. Before proceeding to public coin proofs and showing they are the "same," the book ...
- 3,413
0
votes
0
answers
36
views
Communication complexity in Linear PCP
I wonder how should I state the communication complexity when having a linear PCP combined with another protocol?
May I ask that if I have a protocol that utilizes a linear PCP that has proof length n,...
- 101
0
votes
0
answers
34
views
Why does HyperLogLog use P(at least max zeroes) instead of P(exactly max zeroes)?
In HyperLogLog, we estimate cardinality using the Harmonic Mean of the maximum number of leading zeroes observed across hashed values. The final estimate is derived using P(at least max_zeroes) rather ...
- 1
1
vote
3
answers
213
views
Comparison of Two Algorithms for Finding a Position of 1 in an Array with Equal Zeros and Ones
Given an array 𝑎[1..𝑛] containing half zeros and half ones, we need to find a position in 𝑎 that contains the value 1. Consider the following two algorithms:
Algorithm 1
...
- 11
0
votes
0
answers
75
views
Question Related to Probabilistic Turing Machine
Q) Assume that the success probability of a probabilistic algorithm $M$. In other words, a
probabilistic Turing machine, satisfies $p_{succ} \geq \frac{1}{p(n)}$, for some polynomial $p(n)= O(n^c)$ ...
3
votes
1
answer
137
views
Two-Level (Perfect) Hash Tables in Practice
For $n$ elements, a two-level hash table contains an $O(n)$ top-level hash table whose entries are hash tables also. Each table samples from a 2-universal family. To hash an element $x$, we first hash ...
- 31
4
votes
0
answers
86
views
Approximation algorithm to estimate diameter of points in metric space
Given an arbitrary metric space $M=(X,d)$, is there a $(1+\epsilon)$-approximate algorithm (maybe probabilistic or randomized) that can estimate the diameter of $X$? This algorithm should be faster ...
- 141
1
vote
0
answers
36
views
Distribute and merge HeavyKeeper
I'd like to disribute the HeavyKeeper algorithm. So far I couldn't find resources on how to merge two HeavyKeeper data structures. Is this even possible without scraficing accuracy?
- 111
0
votes
1
answer
54
views
Choosing random sample of requests from stream
Suppose that I would like to divert 10% of requests coming into an API to some other service. The request needs to be sent to the service at the time the request is processed. The requests should be ...
- 131
2
votes
0
answers
50
views
Picking from a categorical distribution such that the selection is stable
Let's say I have a random variable $V$ which takes values from the finite set $V = \{v_1, v_2,...,v_N \}$. I want to pick one value randomly based on given probabilities $p_i = \Pr(V=v_i)$. Let's call ...
- 121
3
votes
1
answer
167
views
Complexity class BPP, but with only expected polynomial running time
The complexity class BPP requires that the running time be guaranteed polynomial, though with only a 2/3 chance of the correct output.
ZPP, on the other hand, guarantees correct output, but now only ...
- 1,081