FST&TCS'97: Seventeenth Conference on

Foundations of Software Technology and Theoretical Computer Science

IIT, Kharagpur, India, December 18 to 20 1997

A Report, by

Pranab Sen, S Venkatesh

The 17th conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS--17) was held from 18th to 20th December, 1997 at the Indian Institute of Technology, Kharagpur. There was a two day pre--conference workshop on Randomised Algorithms, held on 16th and 17th December.

This is the first time that FSTTCS is being held in Kharagpur, and one has to commend the organisers for the smoothness and quiet efficiency with which they conducted the proceedings. The student volunteers put in a lot of effort and they deserve whole--hearted praise. The accommodation was very good with all the participants being put up in various guest houses. All along the hospitality was very warm. Kharagpur is a small town and IIT is situated about five kilometres from the railway station (which boasts of the longest platform in the world --- 988 metres). It is a quiet place, with a huge campus and large open fields. The weather in winter was very pleasant and overall, the atmosphere was very conducive for holding such a conference. Inter--IIT sports meet was being held simultaneously, and this added to the charm of the place.

The workshop has already been covered in Devdatt Dubhashi's report, so here we will concentrate on the conference itself.

The conference featured five invited talks on various topics. Vijaya Ramachandran proposed a new general purpose shared--memory model for Parallel Computation called the Queuing Shared--Memory Model (QSM) and described its advantages in capturing bandwidth limitations occurring in practical parallel machines. Edmund Clarke, using the example of the Space Shuttle, described the role of Model checking in verifying finite--state systems. Deepak Kapur talked on Mechanised verification of a SRT division circuit using a rewrite--based theorem prover, RRL. Madhu Sudan gave a stimulating talk on Algorithmic issues in coding theory . He first surveyed some algebraic constructions of classical codes, and then described a new algorithm for maximum likelihood decoding of Reed Solomon codes beyond the error correction bound. Moshe Vardi examined the problem of Verification of open systems and suggested module checking as a general method for tackling the above problem.

The paper presentation sessions were in general well received by the participants and the attendance was higher as compared to previous conferences (even in the post--lunch sessions!). K.V.Subrahmanyam's talk on Solving discrepancy problems in NC was an interesting follow--up to Edgar's talk in the workshop. V.Arvind in his talk introduced the audience to resource--bounded measure theory and then described their construction of a pseudo--random generator, which extends a key result of Nisan and Wigderson. Vinodchandran showed, in his talk, that various problems such as membership testing etc. for solvable black--box groups are low for the class PP. An unscheduled talk by Tamal on his recent result in FOCS 97 improving the previous upper bound on the possible number of k--sets in the plane was an added attraction and was very well attended. There were many other interesting papers presented at the conference, but the authors are unable to say anything about them for want of technical expertise.

The heavy academic schedule of the conference was lightened by a cultural programme staged in the Netaji hall. It featured a Bharat Natyam performance followed by a Sitar recital, and concluded with a Kathak presentation. All the performances were well appreciated by the audience. The inter--IIT matches added a touch of colour to the proceedings. There was also a football match between guests and hosts which the guests won by two goals to one.

On the whole, our stay at Kharagpur was immensely enjoyable and five days passed off before we realised it. And so it was with a word of thanks to everybody at IIT Kharagpur that we left for Mumbai.