2022 Developer Survey is open! Take survey.

# Tag Info

### 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

### 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
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
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 ...
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^{-...