FSTTCS 2004 at Chennai

By Prahladh Harsha and Jaikumar Radhakrishnan

It was nice to be back in Madras after a long time and even nicer to meet friends from MIT and elsewhere during this year's Foundations of Software Technology and Theoretical Computer Science Conference. FSTTCS is the longest-running international conference on computer science in India, and is organized under the aegis of the Indian Association for Research in Computing Science (IARCS).

The 24th edition was held in Chennai between Dec 16 and Dec 18. The conference was preceded by two workshops on Algorithms for dynamic data (Dec 13 - 14) and Logics for dynamic data (Dec 15). Here are a few statistics about this year's FSTTCS: 38 accepted papers (out of 178 submitted from 38 countries), attendance of about 175 (nearly 35% from outside India). The invited speakers: Pavel Pevzner (UCSD), Javier Esparza (Stuttgart), Piotr Indyk (MIT), John Reynolds (CMU) and Denis Therien (McGill). The proceedings of the conference were published by Springer in LNCS series.

FSTTCS attracts papers in Logics & Semantics and Algorithms & Complexity. Biased by our interests, we attended only the presentations on Algorithms & Complexity. In our view, the highlights were:

• M Fürer, S P Kasiviswanathan, An almost linear time approximation algorithm for the permanent of a random (0-1) matrix.
• A K Ponnuswami, H Venkateswaran, Monotone Boolean circuits for bipartite perfect matching require exponential size.
• L Radamacher, S Vempala, Testing geometric convexity. This paper demonstrates that testing whether a given set S in R^n is convex or far from convex (in the property-testing sense) can be determined by queries, whose number is independent of the actual size of the set S, but is however exponential in the dimension of the space (i.e., n). The set S is presented to the tester by a membership oracle and a random oracle.
• J Hitchcock, A Pavan, Hardness hypotheses, derandomization and circuit complexity. This paper shows that the NP-machine hypothesis is implied by both the Measure hypothesis and pseudo-NP hypothesis. These 3 hypotheses are some of the commonly used hypotheses in derandomization. Furthermore, the authors show that several of the derandomization and circuit lower-bound results that are known to follow from the latter two hypotheses also follow from the NP-machine hypothesis.
• J Kempe, A Kitaev, O Regev, The complexity of the local Hamiltonian problem. The local Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analog of NP. It was known that the 1-local Hamiltonian problem is in P while the k-local Hamiltonian problem is QMA-complete for k >= 3. This paper settles the case for the 2-local Hamiltonian problem and shows that it is also QMA-complete. Thus, the k-local Hamiltonian problem is similar in spirit to MAX-k-SAT which is NP-complete for k > = 2.

Some authors could not attend the conference. The paper Minimum weight pseudo-triangulations by J Gudmundsson and C Levcopolous was presented beautifully by Mark de Berg. The paper on No, coreset, no cry by S Har-Peled, was presented by Kasturi Varadarajan. The author did not get a visa in time from the Chicago consulate (there are some advantages to traveling on an Indian passport), and had sent a recording of his presentation. In the end, Kasturi did a wonderful job using only the slides, but one was left wondering what the video looked like.

Prof. Rani Sirmoney, who turned 75 in July 2004, was honored in a special session at the conference. Prof. Sirmoney is a senior and highly respected theoretical computer scientists in India who works in the area of Formal Languages, Automata Theory, Machine Learning and DNA Computing. She has nurtured several generations of researchers through her teaching and collaborations. In her speech, she thanked her colleagues at the Madras Christian College for their support and encouragement, and mentioned, among other things, that she never faced any gender-based discrimination at that institution.