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-thirds. The thing is, using r random bits one gets only one bit of useful data. Thats not very good. Can we extract more from these random bits? Answer is yes! Thats what extractors are for. He presented Luca trevisan's paper titled Extractors and pseudorandom generators. And here he presented a wonderful concept called: Trevisan Extractor. This literally used all the knowledge built till that date in the course! I will try to scribe something about this and put it up here.
Next we moved to expander graphs. Actually there were student's seminars just before this class. But about that sometime later. So simply speaking expander graphs have low degree but high connectivity. As can be observed, two conflicting parameters are to be achieved. Expander graphs have again turned out to be 'very very' useful tools in complexity theory. Two recent (not too recent anymore) results crucially use expander graphs. The first being Reingold's paper showing SL equals L and the second being Irit Dinur's simpler rpoof for PCP theorem. The discussion on the later has started off from today. While the prior was covered along with things related to exander graphs.
This is a very vague outline, but the plan is I will try to scribe a bit about expanders soon (with little more detail). Apart from that, will try to update about the progress made towards providing PCP theorem. So hopefully this thread will continue.
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-thirds. The thing is, using r random bits one gets only one bit of useful data. Thats not very good. Can we extract more from these random bits? Answer is yes! Thats what extractors are for. He presented Luca trevisan's paper titled Extractors and pseudorandom generators. And here he presented a wonderful concept called: Trevisan Extractor. This literally used all the knowledge built till that date in the course! I will try to scribe something about this and put it up here.
Next we moved to expander graphs. Actually there were student's seminars just before this class. But about that sometime later. So simply speaking expander graphs have low degree but high connectivity. As can be observed, two conflicting parameters are to be achieved. Expander graphs have again turned out to be 'very very' useful tools in complexity theory. Two recent (not too recent anymore) results crucially use expander graphs. The first being Reingold's paper showing SL equals L and the second being Irit Dinur's simpler rpoof for PCP theorem. The discussion on the later has started off from today. While the prior was covered along with things related to exander graphs.
This is a very vague outline, but the plan is I will try to scribe a bit about expanders soon (with little more detail). Apart from that, will try to update about the progress made towards providing PCP theorem. So hopefully this thread will continue.
Comments