21. FSTTCS 2001: Bangalore, India

Invited Papers

• Eric Allender:
  When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity. 1-15
  
• Sanjeev Arora:
  Approximation Schemes for Geometric NP-Hard Problems: A Survey. 16-17
  
• David Harel, Yehuda Koren:
  On Clustering Using Random Walks. 18-41
  
• Colin Stirling:
  An Introduction to Decidability of DPDA Equivalence. 42-56
  
• Uri Zwick:
  Semidefinite Programming Based Approximation Algorithms. 57
  

Contributed Papers

• Manindra Agrawal:
  Hard Sets and Pseudo-random Generators for Constant Depth Circuits. 58-69
  
• Manindra Agrawal:
  The First-Order Isomorphism Theorem. 70-82
  
• Richard J. Anderson, Sampath Kannan, Howard J. Karloff, Richard E. Ladner:
  Thresholds and Optimal Binary Comparison Search Trees. 83-95
  
• Lubos Brim, Ivana Cerná, Pavel Krcál, Radek Pelánek:
  Distributed LTL Model Checking Based on Negative Cycle Detection. 96-107
  
• Cristiano Calcagno, Hongseok Yang, Peter W. O'Hearn:
  Computability and Complexity Results for a Spatial Assertion Language for Data Structures. 108-119
  
• Jianer Chen, Donald K. Friesen, Weijia Jia, Iyad A. Kanj:
  Using Nondeterminism to Design Deterministic Algorithms. 120-131
  
• Zhe Dang, Oscar H. Ibarra, Pierluigi San Pietro:
  Liveness Verification of Reversal-Bounded Multicounter Machines with a Free Counter. 132-143
  
• Axel Dold, Vincent Vialard:
  A Mechanically Verified Compiling Specification for a Lisp Compiler. 144-155
  
• Dana Fisman, Amir Pnueli:
  Beyond Regular Model Checking. 156-170
  
• Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, Hans-Ulrich Simon:
  Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity. 171-182
  
• Neelima Gupta, Sumit Chopra, Sandeep Sen:
  Optimal, Output-Sensitive Algorithms for Constructing Upper Envelope of Line Segments in Parallel. 183-194
  
• Venkatesan Guruswami:
  List Decoding from Erasures: Bounds and Code Constructions. 195-206
  
• Neeraj Jaggi, K. Gopinath:
  Verification of a Leader Election Algorithm in Timed Asynchronous Systems. 207-218
  
• Andreas Jakoby, Christian Schindelhauer:
  Efficient Addition on Field Programmable Gate Arrays. 219-231
  
• Radha Krishnan, Balaji Raghavachari:
  The Directed Minimum-Degree Spanning Tree Problem. 232-243
  
• Tamás Lukovszki, Anil Maheshwari, Norbert Zeh:
  I/O-Efficient Batched Range Counting and Its Applications to Proximity Problems. 244-255
  
• P. Madhusudan, B. Meenakshi:
  Beyond Message Sequence Graphs. 256-267
  
• Monaldo Mastrolilli:
  Grouping Techniques for One Machine Scheduling Subject to Precedence Constraints. 268-279
  
• Mogens Nielsen, Vladimiro Sassone, Jirí Srba:
  Properties of Distributed Timed-Arc Petri Nets. 280-291
  
• Doron Peled, Amir Pnueli, Lenore D. Zuck:
  From Falsification to Verification. 292-304
  
• Erion Plaku, Igor Shparlinski:
  On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems. 305-316
  
• Amir Pnueli, Yoav Rodeh, Ofer Strichman:
  Range Allocation for Equivalence Logic. 317-333
  
• Ashish Tiwari:
  Rewrite Closure for Ground and Cancellative AC Theories. 334-346