Archive for March, 2010

Integer Programming

March 25, 2010

I really don’t like Integer Programming. But I think having the course has had benefits for me:

  1. I figured out that the decision of changing supervisor was a correct one (my former supervisor worked on IP).
  2. I can understand (feel) what one means when she says “I don’t like this course!”
  3. I can evaluate my performance on something that I don’t like but I have to do.

PS – I want to learn beamer for my approximation algorithms presentation. Hoorraay !

Advertisements

Does Coke and Pepsi taste differently?

March 13, 2010

In a talk of John Watrous on Friday in Tutte’s seminar, he proposed the above problem as an interesting example of the power of interactive proofs over classical proofs. To make it precise, suppose that I believe that Coke and Pepsi taste differently plus I can actually feel the difference; and you are really curious if I am right. Well, how can I convince you (give you a “proof”) that they taste differently? The proof needs to have the property that if I am right then you should detect it, and if I am wrong then you should detect it with high probability (say, 99.9 percent).

.

.

.

It is difficult, eh?

.

.

.

No, it is simple. Just make me blindfold, give me 1000 glasses of Coke/Pepsi and I have to categorize them. If I do it correctly, then you will be convinced that I can feel the difference. This is the point: The proof is done by “interaction between you (verifier) and me (prover),” and not by simply giving a certificate (as in the case of classical proof). Well, if I am a liar, then there is a tiny probability that I can fool you; but we usually ignore such small probabilities in life!