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 ...
- 3,357
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.
- 153
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 ...
- 269k
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 ...
- 40
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 ...
- 325
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^{-...
- 269k
Top 50 recent answers are included