CATS'08

Since every blog with some kind of self-respect is reporting from SODA'08, I thought it would be appropriate for this blog to report from CATS'08.

+ Invited talk by Eric Allender. Eric talked about the P vs NP question, and specifically about the question of separating the classes TC0 and NC1. It is known that, for every d, there is a constant c > 1 such that the formula evaluation problem requires TC0 d circuits of size at least nc. Erik argued that it might be possible to obtain a slightly stronger lower bound, showing that there is a c > 1 such that this same set requires uniform TC0 circuits of size nc. Surprisingly this would be sufficient to prove that TC0 is properly contained in NC1.

As a whole the talk was very interesting and at a good level (at least for me). I didn't know much about these classes before and Eric explained all these classes in detail together with a motivation to why they are so important.

+ Business meeting. A few important and positive decisions were made at the business meeting.

James Harland will approach the steering committee of IWOCA to check if it's possible to co-locate IWOCA and CATS in 2010. In my opinion this would be about time. The overlap between the two small communities is too small to warrant two completely separate events.

Next years CATS will include a set of informally invited speakers. That is, a few researchers that would attend anyway will be invited to give a half hour talk about their main research area (or a tutorial). The aim of this is to improve the quality of the talks.

Finally, CATS will encourage further discussions about the accepted papers by making them available on the website and asking for comments on how to improve the papers (results or presentation). Hopefully, this will also encourage more discussion during the presentation.