Tuesday, September 09, 2008

TCS 2008: Invited Speakers for the First Day

I am in Milan for TCS 2008, the bi-annual conference organized by IFIP TC1 in conjunction with the World Computer Congress (WCC). TCS 2008 aims at covering both volume A and volume B TCS, and this year features as many as seven 45-minute invited talks over three days. (IMHO, this is an exceptional number of invited talks for such a short conference.)

Being part of an event like the WCC, which features many events for IT professionals, makes TCS a very expensive TCS conference to attend, and the atmosphere is somewhat different from that of the typical conference TCS folks tend to attend. The early registration fee for an IFIP member was 525 euros (the late one is 680 euros for IFIP members and 800 euros for non-members), it does not include lunches and at the coffee breaks we get just coffee! Not surprisingly attendance at the conference is small and, despite the number of CS departments in Milan and surrounding areas, there are preciously few locals taking part in the event. I guess that there is a definite lesson to be learnt here.

Here I will limit myself to discussing some of the invited talks at the conference. TCS 2008 was kicked off by a presentation delivered by Grzegorz Rozenberg entitled Natural Computing. In his talk, he discussed models of computation inspired by nature and how they differ from classical computational models we use in computer science. I have not found his presentation on line, but you can read Rozenberg's views on the subject of natural computing vis-a-vis classical computer science in his acceptance speech for a honorary degree he received from the University of Bologna as well as in the many (and I really mean "many") technical papers he has written on the topic.

Rozenberg's invited talk was followed by a truly remarkable presentation by Javier Esparza. Javier was one of our invited speakers at ICALP 2008 and I already sang the praises for his presentation in Reykjavík. I really wish that more students had been there to see how to deliver an excellent talk despite a lack of slides for the first ten minutes or so because of technical problems. This was an example of how very good story-telling skills can easily overcome technological failures (at least at the beginning of a technical talk). After all, a conference speaker or a teacher are not so different from ancient story tellers, minstrels or gurus.

Javier's talk reported on results that he has obtained with his students on the solution of monotonic polynomial equations, a subject that one would expect to have been completely settled by mathematicians a long time ago, and that instead has been the source of interesting recent developments in the computer-science literature. The key point here is that one can obtain very strong results on methods for solving polynomial fixed-point equations if one restricts oneself to monotonic equations. I let you browse through Javier's slides since nothing I could write here would do justice to the many exciting results he has achieved with his students. The slide also list some interesting open problems. In particular, consider the problem

MSPE-DECISION: Given an MSPE X = f (X) with rational coefficients and k rational, decide whether the first component of the least solution of that system of monotonic polynomial equations is at most k.

The above problem is in PSPACE and unlikely to be in P. It might be solvable using a polynomial number of arithmetic operations. According to Javier, a proof of this fact would be a sensational result. Some of you might like to sharpen their pencils and try to solve this problem.

I was again pleased to be in the room to listen to yet another inspiring talk by Javier, who is rapidly becoming one of the favourite invited speakers at European TCS conferences.

I will try to report on the other invited talks I heard at some point soon.

No comments: