FSTTCS 2009 December 15-17, 2009, Kanpur, India

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science



Ravi Kannan and K. Narayan Kumar (Eds.)
ISBN 978-3-939897-13-2, LIPICS Vol. 4 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 6 MB)
Search Publication Server

Authors
  • Abdulla, Parosh A.
  • Ammar, Mostafa
  • Arvind, Vikraman
  • Baier, Christel
  • Bessy, Stéphane
  • Bojanczyk, Mikolaj
  • Bozzelli, Laura
  • Braud, Laurent
  • Braverman, Mark
  • Brazdil, Tomas
  • Cabessa, Jérémie
  • Chakrabarty, Deeparnab
  • Chen, Yu-Fang
  • Cook, Stephen
  • Cristau, Julien
  • Datta, Samir
  • Dawar, Anuj
  • Delaune, Stéphanie
  • Demri, Stéphane
  • Duparc, Jacques
  • Esparza, Javier
  • Facchini, Alessandro
  • Fomin, Fedor V.
  • Forejt, Vojtech
  • Gaspers, Serge
  • Georgiou, Konstantinos
  • Grösser, Marcus
  • Hildrum, Kirsten
  • Hitchcock, John M.
  • Holik, Lukas
  • Huang, Chien-Chung
  • Huth, Michael
  • Joglekar, Pushkar S.
  • Jurdzinski, Marcin
  • Kalyanasundaram, Subrahmanyam
  • Kannan, Ravi
  • Kaplan, Marc
  • Kattenbelt, Mark
  • Kerenidis, Iordanis
  • Khandekar, Rohit
  • Kiefer, Stefan
  • Kneis, Joachim
  • Kortsarz, Guy
  • Krcal, Jan
  • Kremer, Steve
  • Kretinsky, Jan
  • Kreutzer, Stephan
  • Kucera, Antonin
  • Kumar, Abhinav
  • Lachish, Oded
  • Langer, Alexander
  • Laplante, Sophie
  • Larsen, Kim G.
  • Lazic, Ranko
  • Legay, Axel
  • Lipton, Richard J.
  • Lodaya, Kamal
  • Lokam, Satyanarayana V.
  • Lokshtanov, Daniel
  • Löding, Christof
  • Madeira, André
  • Magen, Avner
  • McKenzie, Pierre
  • Moors, Adriaan
  • Murlak, Filip
  • Muthukrishnan, S.
  • Narayan Kumar, K.
  • Nimbhorkar, Prajakta
  • Nutov, Zeev
  • Odersky, Martin
  • Parekh, Sujay
  • Patankar, Vijay M.
  • Paul, Christophe
  • Paul, Soumya
  • Pavan, Aduri
  • Pereira, Olivier
  • Perez, Anthony
  • Pinchinat, Sophie
  • Praveen, M.
  • Rabinovich, Alexander
  • Rajan, Deepak
  • Raman, Venkatesh
  • Ravi, R.
  • Roland, Jérémie
  • Rossmanith, Peter
  • Saha, Chandan
  • Santhanam, Rahul
  • Saptharishi, Ramprasad
  • Sarma M. N., Jayalal
  • Sarma, Atish Das
  • Saurabh, Saket
  • Saxena, Nitin
  • Sethuraman, Jay
  • Simon, Sunil
  • Srinivasan, Srikanth
  • Svitkina, Zoya
  • Taly, Ankur
  • Thierauf, Thomas
  • Thomassé, Stéphan
  • Tiwari, Ashish
  • Torunczyk, Szymon
  • Tourlakis, Iannis
  • Tracol, Mathieu
  • Vinodchandran, N. V.
  • Vojnar, Tomas
  • Wagner, Fabian
  • Wehr, Dustin
  • Wigderson, Avi
  • Wolf, Joel
  • Wong, Karianto
    		•

    		  
    Preface -- IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
    Authors: Kannan, Ravi ; Narayan Kumar, K.

    Abstract | Document (348 KB) | BibTeX

    Mediating for Reduction (on Minimizing Alternating Büchi Automata)
    Authors: Abdulla, Parosh A. ; Chen, Yu-Fang ; Holik, Lukas ; Vojnar, Tomas

    Abstract | Document (722 KB) | BibTeX

    Algorithms for Message Ferrying on Mobile ad hoc Networks
    Authors: Ammar, Mostafa ; Chakrabarty, Deeparnab ; Sarma, Atish Das ; Kalyanasundaram, Subrahmanyam ; Lipton, Richard J.

    Abstract | Document (206 KB) | BibTeX

    Arithmetic Circuits and the Hadamard Product of Polynomials
    Authors: Arvind, Vikraman ; Joglekar, Pushkar S. ; Srinivasan, Srikanth

    Abstract | Document (217 KB) | BibTeX

    Kernels for Feedback Arc Set In Tournaments
    Authors: Bessy, Stéphane ; Fomin, Fedor V. ; Gaspers, Serge ; Paul, Christophe ; Perez, Anthony ; Saurabh, Saket ; Thomassé, Stéphan

    Abstract | Document (224 KB) | BibTeX

    On the Memory Consumption of Probabilistic Pushdown Automata
    Authors: Brazdil, Tomas ; Esparza, Javier ; Kiefer, Stefan

    Abstract | Document (126 KB) | BibTeX

    Continuous-Time Stochastic Games with Time-Bounded Reachability
    Authors: Brazdil, Tomas ; Forejt, Vojtech ; Krcal, Jan ; Kretinsky, Jan ; Kucera, Antonin

    Abstract | Document (216 KB) | BibTeX

    Deterministic Automata and Extensions of Weak MSO
    Authors: Bojanczyk, Mikolaj ; Torunczyk, Szymon

    Abstract | Document (213 KB) | BibTeX

    On Timed Alternating Simulation for Concurrent Timed Games
    Authors: Bozzelli, Laura ; Legay, Axel ; Pinchinat, Sophie

    Abstract | Document (156 KB) | BibTeX

    Covering of ordinals
    Authors: Braud, Laurent

    Abstract | Document (147 KB) | BibTeX

    Fractional Pebbling and Thrifty Branching Programs
    Authors: Braverman, Mark ; Cook, Stephen ; McKenzie, Pierre ; Santhanam, Rahul ; Wehr, Dustin

    Abstract | Document (106 KB) | BibTeX

    The Wadge Hierarchy of Max-Regular Languages
    Authors: Cabessa, Jérémie ; Duparc, Jacques ; Facchini, Alessandro ; Murlak, Filip

    Abstract | Document (242 KB) | BibTeX

    Automata and temporal logic over arbitrary linear time
    Authors: Cristau, Julien

    Abstract | Document (123 KB) | BibTeX

    Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space
    Authors: Datta, Samir ; Nimbhorkar, Prajakta ; Thierauf, Thomas ; Wagner, Fabian

    Abstract | Document (121 KB) | BibTeX

    Domination Problems in Nowhere-Dense Classes
    Authors: Dawar, Anuj ; Kreutzer, Stephan

    Abstract | Document (226 KB) | BibTeX

    Simulation based security in the applied pi calculus
    Authors: Delaune, Stéphanie ; Kremer, Steve ; Pereira, Olivier

    Abstract | Document (218 KB) | BibTeX

    The Covering and Boundedness Problems for Branching Vector Addition Systems
    Authors: Demri, Stéphane ; Jurdzinski, Marcin ; Lachish, Oded ; Lazic, Ranko

    Abstract | Document (120 KB) | BibTeX

    Subexponential Algorithms for Partial Cover Problems
    Authors: Fomin, Fedor V. ; Lokshtanov, Daniel ; Raman, Venkatesh ; Saurabh, Saket

    Abstract | Document (196 KB) | BibTeX

    On the Tightening of the Standard SDP for Vertex Cover with $ell_1$ Inequalities
    Authors: Georgiou, Konstantinos ; Magen, Avner ; Tourlakis, Iannis

    Abstract | Document (127 KB) | BibTeX

    Kolmogorov Complexity in Randomness Extraction
    Authors: Hitchcock, John M. ; Pavan, Aduri ; Vinodchandran, N. V.

    Abstract | Document (211 KB) | BibTeX

    Donation Center Location Problem
    Authors: Huang, Chien-Chung ; Svitkina, Zoya

    Abstract | Document (120 KB) | BibTeX

    Non-Local Box Complexity and Secure Function Evaluation
    Authors: Kaplan, Marc ; Kerenidis, Iordanis ; Laplante, Sophie ; Roland, Jérémie

    Abstract | Document (198 KB) | BibTeX

    Verification and Refutation of Probabilistic Specifications via Games
    Authors: Kattenbelt, Mark ; Huth, Michael

    Abstract | Document (291 KB) | BibTeX

    Approximating Fault-Tolerant Group-Steiner Problems
    Authors: Khandekar, Rohit ; Kortsarz, Guy ; Nutov, Zeev

    Abstract | Document (217 KB) | BibTeX

    Bounded Size Graph Clustering with Applications to Stream Processing
    Authors: Khandekar, Rohit ; Hildrum, Kirsten ; Parekh, Sujay ; Rajan, Deepak ; Sethuraman, Jay ; Wolf, Joel

    Abstract | Document (233 KB) | BibTeX

    A Fine-grained Analysis of a Simple Independent Set Algorithm
    Authors: Kneis, Joachim ; Langer, Alexander ; Rossmanith, Peter

    Abstract | Document (121 KB) | BibTeX

    Using Elimination Theory to construct Rigid Matrices
    Authors: Kumar, Abhinav ; Lokam, Satyanarayana V. ; Patankar, Vijay M. ; Sarma M. N., Jayalal

    Abstract | Document (126 KB) | BibTeX

    On Nondeterministic Unranked Tree Automata with Sibling Constraints
    Authors: Löding, Christof ; Wong, Karianto

    Abstract | Document (222 KB) | BibTeX

    Functionally Private Approximations of Negligibly-Biased Estimators
    Authors: Madeira, André ; Muthukrishnan, S.

    Abstract | Document (252 KB) | BibTeX

    Nash Equilibrium in Generalised Muller Games
    Authors: Paul, Soumya ; Simon, Sunil

    Abstract | Document (120 KB) | BibTeX

    Modelchecking counting properties of 1-safe nets with buffers in paraPSPACE
    Authors: Praveen, M. ; Lodaya, Kamal

    Abstract | Document (265 KB) | BibTeX

    Synthesis of Finite-state and Definable Winning Strategies
    Authors: Rabinovich, Alexander

    Abstract | Document (127 KB) | BibTeX

    The Power of Depth 2 Circuits over Algebras
    Authors: Saha, Chandan ; Saptharishi, Ramprasad ; Saxena, Nitin

    Abstract | Document (243 KB) | BibTeX

    Deductive Verification of Continuous Dynamical Systems
    Authors: Taly, Ankur ; Tiwari, Ashish

    Abstract | Document (235 KB) | BibTeX

    Recurrence and Transience for Probabilistic Automata
    Authors: Tracol, Mathieu ; Baier, Christel ; Grösser, Marcus

    Abstract | Document (352 KB) | BibTeX

    Structure and Specification as Sources of Complexity
    Authors: Dawar, Anuj

    Abstract | Document (190 KB) | BibTeX

    Priced Timed Automata: Theory and Tools
    Authors: Larsen, Kim G.

    Abstract | Document (163 KB) | BibTeX

    Fighting bit Rot with Types (Experience Report: Scala Collections)
    Authors: Odersky, Martin ; Moors, Adriaan

    Abstract | Document (307 KB) | BibTeX

    Iterative Methods in Combinatorial Optimization
    Authors: Ravi, R.

    Abstract | Document (129 KB) | BibTeX

    Randomness extractors -- applications and constructions
    Authors: Wigderson, Avi

    Abstract | Document (118 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI