FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science: 23rd Conference, Mumbai, India, December 15-17, 2003. Proceedings

Front Matter....Pages -
A Cryptographically Sound Security Proof of the Needham-Schroeder-Lowe Public-Key Protocol....Pages 1-12
Constructions of Sparse Asymmetric Connectors....Pages 13-22
A Separation Logic for Resource Distribution....Pages 23-37
An Equational Theory for Transactions....Pages 38-49
Axioms for Regular Words....Pages 50-61
1-Bounded TWA Cannot Be Determinized....Pages 62-73
Reachability Analysis of Process Rewrite Systems....Pages 74-87
Pushdown Games with Unboundedness and Regular Conditions....Pages 88-99
Real-Time Model-Checking: Parameters Everywhere....Pages 100-111
The Caucal Hierarchy of Infinite Graphs in Terms of Logic and Higher-Order Pushdown Automata....Pages 112-123
Deciding the Security of Protocols with Diffie-Hellman Exponentiation and Products in Exponents....Pages 124-135
Subtyping Constraints in Quasi-lattices....Pages 136-148
An Improved Approximation Scheme for Computing Arrow-Debreu Prices for the Linear Case....Pages 149-155
Word Equations over Graph Products....Pages 156-167
Analysis and Experimental Evaluation of a Simple Algorithm for Collaborative Filtering in Planted Partition Models....Pages 168-182
Comparing Sequences with Segment Rearrangements....Pages 183-194
On Logically Defined Recognizable Tree Languages....Pages 195-207
Randomized Time-Space Tradeoffs for Directed Graph Connectivity....Pages 208-216
Distance-Preserving Approximations of Polygonal Paths....Pages 217-228
Joint Separation of Geometric Clusters and the Extreme Irregularities of Regular Polyhedra....Pages 229-243
On the Covering Steiner Problem....Pages 244-251
Minimality Results for the Spatial Logics....Pages 252-264
Algorithms for Non-uniform Size Data Placement on Parallel Disks....Pages 265-276
Efficient Algorithms for Abelian Group Isomorphism and Related Problems....Pages 277-288
Quasi-polynomial Time Approximation Algorithm for Low-Degree Minimum-Cost Steiner Trees....Pages 289-301
Model Checking and Satisfiability for Sabotage Modal Logic....Pages 302-313
Merging and Sorting By Strip Moves....Pages 314-325
The Macro Tree Transducer Hierarchy Collapses for Functions of Linear Size Increase....Pages 326-337
Distributed Games....Pages 338-351
Maintenance of Multidimensional Histograms....Pages 352-362
Tagging Makes Secrecy Decidable with Unbounded Nonces as Well....Pages 363-374
Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties....Pages 375-386
On the Greedy Superstring Conjecture....Pages 387-398
Reasoning about Infinite State Systems Using Boolean Methods....Pages 399-407
Stringent Relativization....Pages 408-419
Component-Based Construction of Deadlock-Free Systems....Pages 420-433
Moderately Hard Functions: From Complexity to Spam Fighting....Pages 434-442
Zigzag Products, Expander Constructions, Connections, and Applications....Pages 443-443
Back Matter....Pages -