The Student Talks have picked up decent pace. Vipul did a great job in organising it; hats off to him.

Talks given/upcoming: (reverse chronological)

1. Arithmetic Circuits and Identity Testing(23rd October 2008)
   An analogue of a boolean circuit is what is known as an arithmetic circuit, consisting of plus (+) and mult (x) gates. The arithmetic circuit computes some polynomial function of the input variables. In this talk, we try and understand the class of polynomials that are computable by arithmetic circuits of certain parameters and a fundamental problem called Identity Testing.
2. Error Correcting Codes:(29th September 2008)
   Consider a scenario where Alice wants to send a certain message to Bob through a noisy channel. The channel is noisy in the sense that it might corrupt parts of the message flowing throwing it. We want to create a scheme by which Alice can "encode" her message in some way and send it across so that even if Bob receives a slightly corrupted version of the encoding, he can "error correct" to retrieve the message. An encoding function that achieves this is called an Error-Correcting code.
   In this talk, we shall look a couple of such error correcting codes, namely Reed-Solomon and Reed-Muller, and efficient decoding algorithms. If time permits, I shall try to give you some applications of this in complexity.
3. The Goldreich-Levin Theorem:(15th September 2008)
   In this talk, we looked at a very powerful result in Complexity Theory called the Goldreich-Levin algorithm. The problem could be looked at as a list decoding of the hadamard code, or just as an algorithm to find a hidden vector given a blackbox. We shall look at the original proof of the Goldreich-Levin theorem and some important consequences in Complexity.
4. A Crash Course in Probability:(11th September 2008)
   We just looked a few tools from probability that is widely used in computer science. The topics I covered were:
   • Definition of a random variable, expectation, variance, standard deviation
   • The probabilistic method
   • Markov Inequality, Chebychev Inequality and Chernoff's Bound
   • Limited independence, its construction, and applications of it in certain algorithms like MAXCUT and MAX3SAT.
5. Who is the winner? - Combinatorial Games and Strategies:(1st September 2008)
   In this talk we looked at a variety of combinatorial games and understanding winning strategies. Though in some instances could be easy, there are games which are fairly non-trivial to find a strategy. By the end of the talk, we would see a very nice result called the Sprague-Grundy theorem which lets you find winning strategies for a huge class of such combinatorial games.
6. The Banach-Tarski Paradox: (11th August 2008)
   Though the axiom of choice looks very innocent, it has some crazy consequences, one of them being the Banach-Tarski Paradox:
   Given a solid sphere of radius 1, it can broken up into a finite number of pieces (current best known number is 6), rearranged with just translations and rotations to form two solid spheres of radius 1.
   In this talk, I gave a proof of it (with about 20 pieces).
The source files for the pdf are available here.
7. Chronicles of Planet Lambda - Reflection, The Final Frontier:(4th April 2007)
   The final talk of the series, the focus was on reflection of self-interpretters in lambda terms. The talk was predominantly be on a recent result by John Tromp and some improvements on it (stemmed off my recent work with Dr V Vinay).
8. Chronicles of Planet Lambda - The Return of the Birds:(7th March 2007)
   This is the second talk in the series of three. Here I spent time on combinators (or birds as in Smullyan's book), some nice theorems on them and also the traditional bases for lambda calculus. The talk ended with a motivation to self-interpretters in lambda calculus which would be discussed in detail in the next talk.
9. Chronicles of Planet Lambda - First Contact:(14th February 2007)
   This was the first of the series of 3 talks. It was a first course on lambda calculus, defined lambda terms and combinators. Then went on to emulating boolean algebra and arithmetic (church numerals) and the primitive data structures of tuples and lists.
   I spent quite some time to motivate fixed point combinators, systematic constructions of them, tried to make it as exciting as possible. I did rush at the end since the shuttle was leaving, will go over them again in the next talk.
10. Majority with Inverse Polylog Promise :(Jan 31st, 2007)
    As a sequel to my previous talk on sorting networks and majority, I discussed the result of Ajtai-BenOr on an inverse polylog advantage for majority. And since I had also hinted about some communication complexity approaches, the talk also included some circuit complexity through the complexity of additions of numbers.
    The slides were not completed during the talk, I used the board for most of it. I shall put up the links once the slides are ready.
11. The AKS Primality Test:(Jan 17th, 2007)
    The name says it all, I presented the AKS polynomial time test for primality of a number. I plan to make it as simple as possible, using the Jaikumar-Vinay-Kavitha article. The source files are available here.
    I had gone extremely fast in the talk, so in order to remove any hand-wavings/missing details in the talk, I also sent the students a informal writeup on it.
12. Sorting Networks and Threshold Functions of Small Depth:(Nov 9, 2006)
    This is a presentation with a formal guise, no stories. NC² sorting networks are first explored, and then we move into Valiant's NC¹ circuit for Majority. I initially intended to discuss the AKS sorters and amplifying inverse log advantage in constant depth as well but I think I'd be doing that the sequel.
    The source files are available here
13. Which Game is Harder?:(Sep 6, 2006)
    This is just an introduction to the "popular" complexity classes. Later we get into computability of boolean functions and "random" strings in the Chaitin-Kolmogorov setting. The classes are introduced using some popular games available on the computer and examining the resource bounds to "solve" them; randomness of strings are also introduced in a similar context.
    The source files are available here.
    
14. An "Electric" Story of a Drunkard:(Sep 1, 2006)
    I presented a proof of one of the theorems of Polya on simple random walks on integer lattices (also known as the drunkard's walk), by calculating effective resistance of related circuits. It is a very neat proof, originally given by Doyle and Snell in a manuscript.
    The source files are available here.

Vipul has the list of all the talks given by the students on his page. It is currently maintained by Kshitij here.