New answers tagged randomized-algorithms
0
votes
Is there an algorithm for mapping two ambiguous and unrelated data sets?
For discrete, non numerical data, you can use a relation (in the sense of relational database).
For numerical data, you can use multivariate interpolators, such as neural nets with overfitting.
What ...
2
votes
Are there any freely available resources to study randomized algorithms?
A few days ago, my tutor recommend Stanford cs265 to me. I have read some lectures and watched some videos, I think it's really a great course for those who want to study randomized algorithm.
0
votes
Accepted
The universal relation problem in communication complexity
If public randomness is allowed, then the two parties apply a common random permutation on their inputs, and XOR their inputs with a common random string.
Suppose that the inputs are $x,y$, and that ...
1
vote
Are there any freely available resources to study randomized algorithms?
I can recommend you the book from Michael Mitzenmacher and Eli Upfal called "Probability and Computing". I bought a hard copy of it recently and I absolutely don't regret it. It's very ...
2
votes
Accepted
Randomized Algorithm Lemma
To prove the claim
$$
P(Mr = 0 ) \leq \frac{1}{2}
$$
it is enough to prove it for any row vector $m = (M_{i,1},...,M_{i,n})$ that has at least one non-zero coefficient. Thus, we continue by induction ...
3
votes
Accepted
Question about what exponentially small probability of success means in randomized algorithms
A quantity is exponentially small (with respect to parameter $n$) if it is $\Omega(\alpha^n)$ and $O(\beta^n)$ for some $\alpha,\beta \in (0,1)$.
A quantity is polynomially small if it is $\Omega(n^{-...
Top 50 recent answers are included
Related Tags
randomized-algorithms × 396algorithms × 180
probability-theory × 72
complexity-theory × 49
algorithm-analysis × 46
randomness × 43
graphs × 33
probabilistic-algorithms × 22
time-complexity × 19
approximation × 18
data-structures × 15
sorting × 15
sampling × 15
monte-carlo × 12
runtime-analysis × 11
combinatorics × 11
optimization × 10
quicksort × 10
pseudo-random-generators × 10
complexity-classes × 9
streaming-algorithm × 9
terminology × 8
computational-geometry × 8
arrays × 8
random-number-generator × 8