2022 Developer Survey is open! Take survey.

New answers tagged

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 ...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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^{-...
user avatar

Top 50 recent answers are included