FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science

1. Front Matter

   Pages I-XI

   PDF

2. Invited Papers

   1. When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity

      • Eric Allender

      Pages 1-15

   2. Approximation Schemes for Geometric NP-Hard Problems: A Survey

      • Sanjeev Arora

      Pages 16-17

   3. On Clustering Using Random Walks

      • David Harel, Yehuda Koren

      Pages 18-41

   4. An Introduction to Decidability of DPDA Equivalence

      • Colin Stirling

      Pages 42-56

   5. Semidefinite Programming Based Approximation Algorithms

      • Uri Zwick

      Pages 57-57

3. Contributed Papers

   1. Hard Sets and Pseudo-random Generators for Constant Depth Circuits

      • Manindra Agrawal

      Pages 58-69

   2. The First-Order Isomorphism Theorem

      • Manindra Agrawal

      Pages 70-82

   3. Thresholds and Optimal Binary Comparison Search Trees

      • Richard Anderson, Sampath Kannan, Howard Karloff, Richard E. Ladner

      Pages 83-95

   4. Distributed LTL Model Checking Based on Negative Cycle Detection

      • Luboš Brim, Ivana Černá, Pavel Krčál, Radek Pelánek

      Pages 96-107

   5. Computability and Complexity Results for a Spatial Assertion Language for Data Structures

      • Cristiano Calcagno, Hongseok Yang, Peter W. O’Hearn

      Pages 108-119

   6. Using Nondeterminism to Design Efficient Deterministic Algorithms

      • Jianer Chen, Donald K. Friesen, Weijia Jia, Iyad A. Kanj

      Pages 120-131

   7. Liveness Verification of Reversal-Bounded Multicounter Machines with a Free Counter

      • Zhe Dang, Oscar H. Ibarra, Pierluigi San Pietro

      Pages 132-143

   8. A Mechanically Verified Compiling Specification for a Lisp Compiler

      • Axel Dold, Vincent Vialard

      Pages 144-155

   9. Beyond Regular Model Checking

      • Dana Fisman, Amir Pnueli

      Pages 156-170

   10. Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity

       • Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, Hans Ulrich Simon

       Pages 171-182

   11. Optimal, Output-Sensitive Algorithms for Constructing Upper Envelope of Line Segments in Parallel

       • Neelima Gupta, Sumit Chopra, Sandeep Sen

       Pages 183-194

   12. List Decoding from Erasures: Bounds and Code Constructions

       • Venkatesan Guruswami

       Pages 195-206

   13. Verification of a Leader Election Algorithm in Timed Asynchronous Systems

       • Neeraj Jaggi, K. Gopinath

       Pages 207-218

   14. Efficient Addition on Field Programmable Gate Arrays

       • Andreas Jakoby, Christian Schindelhauer

       Pages 219-231

This volume contains the proceedings of the 21st international conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2001), organized under the auspices of the Indian Association for Research in Computing Science (IARCS). This year’s conference attracted 73 submissions from 20 countries. Each s- mission was reviewed by at least three independent referees. In a departure from previous conferences, the ?nal selection of the papers making up the program was done through an electronic discussion spanning two weeks, without a physical meeting of the Program Committee (PC). Since the PC of FSTTCS is distributed across the globe, it is very di?cult to ?x a meeting whose time and venue is convenient for a substantial fraction of the PC. Given this, it was felt that an electronic discussion would enable all members to participate on a more equal footing in the ?nal selection. All reviews, scores, and comments were posted on a secure website, with a mechanism for making updates and automatically sending noti?cations by email to relevant members of the PC. All PC members participated actively in the discussion. The general feedback on the arrangement was very positive, so we hope to continue this in future years. We had ?ve invited speakers this year: Eric Allender, Sanjeev Arora, David Harel, Colin Stirling, and Uri Zwick. We thank them for having readily accepted our invitation to talk at the conference and for providing abstracts (and even full papers) for the proceedings.

• algorithm
• algorithms
• complexity
• computer
• computer science
• data structure
• data structures
• formal verification
• logic
• model checking
• petri net
• verification

• Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India

  Ramesh Hariharan, V. Vinay

• Chennai Mathematical Institute, Chennai, India

  Madhavan Mukund

Policies and ethics