Archive for the ‘story’ Category

The story of my paper with Noga Alon

October 15, 2010

Well, in one of our meetings in August, Nick (my supervisor) told me that Noga Alon will visit UWaterloo in a few weeks, and I can give him a quick glimpse of my work on Cops and Robber game, and I said Ok, happy to know that I’ll meet him. He came in September and gave a talk in Tutte’s seminar. Next day Nick arranged a meeting in his office and I told Noga my work. He seemed interested, and proposed an idea that if correct, would’ve extended my result. With Nick’s help I worked on the idea for a week or two, and yeaaah … it worked! I was so excited, sent the proof to Nick, and he verified its correctness. Then I contacted Noga and asked if he’d like to be a coauthor, and he confirmed. He made a bunch of corrections and we submitted it. It’s a short paper however (7 pages).

Oh boy, if you’d told me an year ago that just an year after coming to Canada I’ll write a paper with Noga Alon, I would’ve considered it as a joke. But it really happened! Thank you God!

Some technical details: There was a recent preprint by Frieze et al., where they had considered the variation of Cops and Robber where the robber has speed s>1. For every s they had given a lower bound for the maximum cop number of a graph with n vertices in that variation. In summer I had worked on this problem and improved their bound for s<7 (here). I proved the cop number of an n-vertex graph can be as large as n^{s/s+1} when s=2,4. My proof uses regular graphs with large girth, which are called cages. I had also conjectured that this lower bound holds for larger values of s as well. There is an old conjecture of Bollobas about cages that implies my conjecture. Noga told me about regular graphs that don’t have large girths, but for every two close vertices, there are a constant number of shortest paths connected them. These graphs are enough for my proof, and their number of vertices are exactly what I wanted. Hoorraay.

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 !

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!

The PCP Theorem, and computational complexity

February 8, 2010

One reason I like computational complexity is because it’s mysterious: you see surprising results that don’t agree with your common sense. The first example was the equality NL = co-NL, which I saw a few years ago, and has a very elegant proof. And the second example was the PCP e, i.e. NP = PCP (log n, 1), which is quite surprising, and the proof is perhaps very complicated. That’s why you can never be sure that NP\P is nonempty, even if  everyone believes it.

For almost the same reason, I liked probability theory when I was in high-school: it is mysterious, and there were lots of paradoxical problems related to probability. Well, when I studied formal probability theory (Kolmogorov axioms etc.) there wasn’t any paradoxes anymore (fortunately?), but I still like it, because of its surprisingly strong applications in graph theory and algorithms.