Potpourri

I will try to start a Friday for movies session. I am not sure how much it will run, given that in this city hardly any new movies are released 2-3 months after the world releases. Anyhow, I will keep to old as well as new movies for this session to run a bit longer than my enthusiam. So let me start with a movie called "The saddest music in the world". The movie released in 2003. The original screenplay is by the Japanese author Kuzao Ishiguro. (Author of Remains of the day.) It is set in Canada, at the time of the American Great Depression. A leg-less business woman, having business of beer, arranges a international contest of saddest music. Many countries are encouraged to participate in the contest and to perform a music piece. This is a great business move for her, because in middle of depression, when everybody is suffering, the saddest song contest wins her a great business. Many people come to watch the contest and ofcourse buy her beer. She announces at the beginnin...

I had started writing about Arvind's class that I am attending this semester. Well, I hardly said anything about it. But let me reopen the topic. We are almost 3 months down the course and arvind covered a good number of topics. In error correcting codes he discussed about Varshamov's bound, Reed-solomon codes, concatenated codes, Justesen codes and decodings of these. As he kept reminding, the theory of error correcting codes has proved very useful for complexity theory. He proved the Impagliazzo-Wigderson '97, theorem as a corollary to the theory built here. He introduced list-decoding of Reed-Solomon codes and proved Madhusudan '97 theorem (if it can be called that) using this technique. With these two applications of error correcting codes to complexity theory, he moved on to the extractors. To motivate extractors: Think of a random algorithm A. Say on input x, of length n, it makes r random coin tosses. Say A gives a correct value with probability greater than two-...