Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I will be happy for a clue.

I need to find a randomized algorithm with probability of $3/4$ and no more of $O(\log(n))$ bit's that send from A to B.

A and B holding strings $as=(a_0,....a_{n-1})$ $bs=(b_0,....,b_{n-1})$. A is composed from 0,1 only, and B is composed from 0, 1, $t$, where $t$ can be 0 or 1. meaning: as=(001001) bs=(0t10tt) are identical. A sends only one massage, and B need to decided if $as=bs$.

If we know that $|t|=1$, I need to find a randomized algorithm with probability of $3/4$ to solve this problem. What I think to do is algorithm, based on Rabin-Karp algorithm, and run it twice - change $t$ to 1, and change $t$ to 0. The algorithm will do the next steps: A will choose coincidental number (q) from 1 to $n^2$, and will calculate $r="as" \mod q$. it will send to B (q and r), and B will do the same (will calculate "bs" mod q, and will mark the answer as j). If j=r - then B will say identical, otherwise he will say "not identical". I succeeded to prove that if B will check his string in one of the cases (t=0 ot t=1), it will give a correct number with probability of $3/4$. But when I running it twice, I have a problem. Because I have more words to make a mistake with, and I successes only with probability of $1/2$.

After it I asked to give an algorithm if $t=|5\log(n)|$, and I thought to run it like with t=1, but I didn't succeed to improve the probability of that.

Thank you a lot for your help.

share|cite|improve this question
I suspect you may need to explain this more systematically to get an answer. What do $|t|=1$ and $t=|5\log(n)|$ mean? What messages can A send? What's a coincidental number? etc. – joriki May 19 '11 at 12:42
@joriki. Thank you for your answer. A can send any message but no more of O(log(n)) bits. So in my answer, it will send 2 numbers: r and q. |t| is the numbers of dontcare which appear in the string "bs". If I have |t|=1, then b can be:"1000t11" or "1t110". t can be 1 or 0 (donrcare..). meaning - if "bs" is 00110 then 00t10 and 0t110 are identical strings to "bs", but 01t10 no. if |t|=4, then "bs" can be 10tt1t11t. coincidental number: I mean randomize prime number. Thanks. – Amir May 19 '11 at 13:12
So I take it $t=|5\log(n)|$ should be $|t|=5\log(n)$? – joriki May 19 '11 at 16:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.