The 2024 Developer Survey results are live! See the results

# Questions tagged [probabilistic-algorithms]

Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.

216 questions
Filter by
Sorted by
Tagged with
28 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
52 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 ...
40 views

### Approximate Set Intersection datastructure

I'm working on a project involving set-like data structures. For one of the algorithms I am using that does a merge-like operation on two of these structures I can take a very big shortcut if I know ...
1 vote
25 views

### Information on sample pooling strategies

I am looking for information about a specific sort of problem: There is a set of samples, and some subset of them are positive. It is possible to combine samples and test if the combination contains ...
• 183
61 views

### Generate random points such that no 4 lie on a circle

In $\tilde{O}(n)$ time, can I generate $n$ random lattice points so that no four lie on the same circle? You can assume we pick points from a grid of side length $k \gg n$ (say, take $k=n^2$). I have ...
40 views

### If $NP \subseteq BPP$ then $NP = RP$. Confusion on the probability that M gives at least one wrong answer in BPP in n invocations

I was looking at the proof of if $NP \subseteq BPP$ then $NP = RP$ here. At the end of the proof the author states: "Note that if $M$ always gives correct answers on calls to $M$, then when $\phi$...
34 views

### A probabilistic data structure based on flipping bits with probability $\frac{1}{2^x}$ for counting

How does this data structure work and what is its application? ...
36 views

### Understanding the last algebra step of this proof

Could someone help me understand why in the below proof, if $k > log_{2}n$, then $P(N_i=1)< \frac{1}{n}$?
30 views

### What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?

Suppose a polynomial time machine that has an access to a polynomially long string of bits independent on the input. On average, it's impossible to compress this string to a subpolynomially long ...
• 1,881
26 views

• 113
96 views

### Is NP=RP(2^-n)?

I believe its true but struggle to prove. I know NP=union over positive c's of RP(2^-(n^c)) and from here to prove that RP(1/2^n) contained in NP is immediate. the other side is the problem. I've ...
1 vote
48 views

### How can $R_HL$ differ from $RL$?

https://complexityzoo.net/Complexity_Zoo:R RL: Randomized Logarithmic-Space Has the same relation to L as RP does to P. The randomized machine must halt with probability 1 on any input. It must also ...
• 249
112 views

• 105
478 views

### Why is tabulated hashing 3-wise independent but not 4-wise independent?

Tabulated hashing uses tables of random numbers to compute hash values. Suppose $|\mathcal{U}| = 2^w \times 2^w$ and $m = 2^l$, so that the items being hashed are pairs $(x,y)$ where $x$ and $y$ are \$...
• 141