IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science
December 9 to 11, 2008, Bangalore, India

List of accepted papers

1. Omid Amini, Fedor Fomin and Saket Saurabh
   Implicit Branching and Parameterized Partial Cover Problems
2. Takahito Aoto
   Sound Lemma Generation for Proving Inductive Validity of Equations
3. Vikraman Arvind and Pushkar Joglekar
   Some Sieving Algorithms for Lattice Problems
4. Mohamed Faouzi Atig, Ahmed Bouajjani and Tayssir Touili
   Analyzing Asynchronous Programs with Preemption
5. David Basin, Felix Klaedtke, Samuel Müller and Birgit Pfitzmann
   Runtime Monitoring of Metric First-order Temporal Properties
6. Noam Berger, Nevin Kapur, Leonard J Schulman and Vijay Vazirani
   Solvency Games
7. Dietmar Berwanger and Laurent Doyen
   On the power of imperfect information
8. Didier Caucal
   Boolean algebras of unambiguous context-free languages
9. André Chailloux and Iordanis Kerenidis
   Increasing the power of the verifier in Quantum Zero Knowledge
10. Krishnendu Chatterjee, Luca de Alfaro, Rupak Majumdar and Vishwanath Raman
    Algorithms for Game Metrics
11. Chandra Chekuri and Nitish Korula
    Single-Sink Network Design with Vertex Connectivity Requirements
12. Chandra Chekuri and Nitish Korula
    Pruning 2-Connected Graphs and Applications
13. Julien Cristau and Florian Horn
    Graph Games on Ordinals
14. Samir Datta, Nutan Limaye and Prajakta Nimbhorkar
    3-connected Planar Graph Isomorphism is in Log-space
15. Josep Diaz, Lefteris Kirousis, Dieter Mitsche and Xavier Perez-Gimenez
    A new upper bound for 3-SAT
16. Rayna Dimitrova and Bernd Finkbeiner
    Abstraction Refinement for Games with Incomplete Information
17. Alan Frieze and Ravindran Kannan
    A new approach to the planted clique problem
18. Daniel Golovin, Anupam Gupta, Amit Kumar and Kanat Tangwongsan
    All-Norms and All-L_p-Norms Approximation Algorithms
19. Stefan Gulan and Henning Fernau
    An Optimal Construction of Finite Automata from Regular Expressions
20. Jonathan Hayman and Glynn Winskel
    The unfolding of general Petri nets
21. Florian Horn
    Explicit Muller Games are PTIME
22. Kazuhiro Inaba and Sebastian Maneth
    The Complexity of Tree Transducer Output Languages
23. Sampath Kannan, Sanjeev Khanna and Sudeepa Roy
    STCON on Directed Unique-Path Graphs
24. Telikepalli Kavitha
    Dynamic matrix rank with partial lookahead
25. Christian Komusiewicz and Johannes Uhlmann
    A Cubic-Vertex Kernel for Flip Consensus Tree
26. Markus Lohrey
    Leaf languages and string compression
27. Georg Moser, Andreas Schnabl and Johannes Waldmann
    Complexity Analysis of Term Rewriting Based on Matrix and Context Dependent Interpretations
28. Romain Péchoux and Jean-Yves Marion
    Analyzing the Implicit Computational Complexity of object-oriented programs
29. Juan Rodriguez-Hortala
    A Hierarchy of Semantics for Non-deterministic Term Rewriting Systems
30. Ashutosh Trivedi and Marcin Jurdzinski
    Average-Time Games