Links to Complexity Blogs

Blogs are an interesting way to dissemate information, since it's informal and allows for comments. Here are some interesting blogs about Theoretical Computer Science.

1. Lance Fortnow's Complexity Blog : The blog for news about complexity theory and other theory related topics.

2. Scott Aaronson's Blog : Scott Aaronson is probably the most promising researcher in computer science now. He is also very funny, and his blog makes for a good read.

3. Luca Trevisan's Blog : Luca Trevisan is another shining star from Berkeley. His blog is a bit more techincal that the above ones.

These blogs tend toward Mathematics: Terence Tao's Blog, Gil Kalai's Blog, Tim Gower's Blog.

Lecture 2 - Models of Computation / Discrete Probability

Today, we will look at formalising our model of computation, meaning, we will come up with abstract models to represent our notion of a computing device. We will consider two of the most popular, natural and powerful models, namely, circuits and finite automata.

In the latter half of the lecture, we will learn some basics of discrete probability, which we will need for our next lecture.

The notes for the models of computation are available here. The notes for the discrete probability lecture are from here.

The intro lecture

We discussed the implications of looking at Computation as an abstract notion, and about formalising the notion of efficiency. Today, we looked at the demarcation between efficient and intractable problems and got ourselves comfortable with the notion of "polynomial time" algorithms. We also looked at the powerful idea of the "reduction" and saw how there is a non-trivial transformation from the familiar 3-SAT problem to the Vertex Cover problem. We also looked at a very gentle introduction to the notion of NP-Completeness.

We used the wonderful notes for the first lecture from this.

Deep Thought

Priya and I began a series of 3 lectures, aimed as a gentle introduction to Theoretical CS in general and Complexity Theory in particular at R V College of Engineering, Bangalore last week. Our intention is to get the students, all undergraduates in their 2nd year of studies, to think about CS as a branch of mathematics, something profound and not limited to programming.

Select lecture notes from Luca Trevisan's Complexity Theory course from UC Berkeley and Scott Aaronson's Great Ideas in Theoretical Computer Science course from MIT are being used as handouts to the students.