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.
Author(s): Eric Allender (auth.), Ramesh Hariharan, V. Vinay, Madhavan Mukund (eds.)
Series: Lecture Notes in Computer Science 2245
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2001
Language: English
Pages: 352
Tags: Logics and Meanings of Programs; Programming Languages, Compilers, Interpreters; Mathematical Logic and Formal Languages; Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Discrete Mathematics in Computer Scienc
When Worlds Collide: Derandomization, Lower Bounds, and Kolmogorov Complexity....Pages 1-15
Approximation Schemes for Geometric NP-Hard Problems: A Survey....Pages 16-17
On Clustering Using Random Walks....Pages 18-41
An Introduction to Decidability of DPDA Equivalence....Pages 42-56
Semidefinite Programming Based Approximation Algorithms....Pages 57-57
Hard Sets and Pseudo-random Generators for Constant Depth Circuits....Pages 58-69
The First-Order Isomorphism Theorem....Pages 70-82
Thresholds and Optimal Binary Comparison Search Trees....Pages 83-95
Distributed LTL Model Checking Based on Negative Cycle Detection....Pages 96-107
Computability and Complexity Results for a Spatial Assertion Language for Data Structures....Pages 108-119
Using Nondeterminism to Design Efficient Deterministic Algorithms....Pages 120-131
Liveness Verification of Reversal-Bounded Multicounter Machines with a Free Counter....Pages 132-143
A Mechanically Verified Compiling Specification for a Lisp Compiler....Pages 144-155
Beyond Regular Model Checking....Pages 156-170
Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity....Pages 171-182
Optimal, Output-Sensitive Algorithms for Constructing Upper Envelope of Line Segments in Parallel....Pages 183-194
List Decoding from Erasures: Bounds and Code Constructions....Pages 195-206
Verification of a Leader Election Algorithm in Timed Asynchronous Systems....Pages 207-218
Efficient Addition on Field Programmable Gate Arrays....Pages 219-231
The Directed Minimum-Degree Spanning Tree Problem....Pages 232-243
I/O-Efficient Batched Range Counting and Its Applications to Proximity Problems....Pages 244-255
Beyond Message Sequence Graphs....Pages 256-267
Grouping Techniques for One Machine Scheduling Subject to Precedence Constraints....Pages 268-279
Properties of Distributed Timed-Arc Petri Nets....Pages 280-291
From Falsification to Verification....Pages 292-304
On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems....Pages 305-316
Range Allocation for Equivalence Logic....Pages 317-333
Rewrite Closure for Ground and Cancellative AC Theories....Pages 334-346
