FSTTCS 2013 December 12-14, 2013, Guwahati, India

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)



Anil Seth and Nisheeth K. Vishnoi (Eds.)
ISBN 978-3-939897-64-4, LIPICS Vol. 24 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 20 MB)
Search Publication Server

Authors
  • Agarwal, Archita
  • Akshay, S.
  • Arora, Sonika
  • Bampis, Evripidis
  • Basavaraju, Manu
  • Baskar, Anguraj
  • Bertrand, Nathalie
  • Bodini, Olivier
  • Brázdil, Tomás
  • Calin, Georgel
  • Chakaravarthy, Venkatesan T.
  • Chalermsook, Parinya
  • Chandran, L. Sunil
  • Chen, Taolue
  • Chitnis, Rajesh
  • Choudhury, Anamitra Roy
  • Clairambault, Pierre
  • Consuegra, Mario E.
  • Crowston, Robert
  • Derevenetc, Egor
  • Dinca, Ionut
  • Esparza, Javier
  • Fernau, Henning
  • Fijalkow, Nathanaël
  • Fomin, Fedor V.
  • Forejt, Vojtech
  • Fournier, Paulin
  • Francis, Mathew C.
  • Genest, Blaise
  • Genitrini, Antoine
  • Golovach, Petr A.
  • Goyal, Prachi
  • Grohe, Martin
  • Gupta, Neelima
  • Guruswami, Venkatesan
  • Haar, Stefan
  • Haddad, Axel
  • Haddad, Serge
  • Hague, Matthew
  • Harsha, Prahladh
  • Hofmann, Martin
  • Hofman, Piotr
  • Holzer, Andreas
  • Huang, Chien-Chung
  • Jain, Rahul
  • Jezequel, Loig
  • Jones, Mark
  • Kavitha, Telikepalli
  • Khodamoradi, Kamyar
  • Khot, Subhash
  • Kononov, Alexander
  • Krebs, Andreas
  • Kreutzer, Stephan
  • Krishnamurti, Ramesh
  • Lasota, Slawomir
  • Letsios, Dimitrios
  • Li, Jian
  • Limaye, Nutan
  • Löding, Christof
  • Lucarelli, Giorgio
  • Majumdar, Rupak
  • Manea, Florin
  • Maubert, Bastien
  • Mayr, Richard
  • Mehlhorn, Kurt
  • Melliti, Tarek
  • Meyer, Roland
  • Michail, Dimitrios
  • Misra, Neeldhara
  • Muciaccia, Gabriele
  • Mukherjee, Koyel
  • Müller, Mike
  • Murawski, Andrzej S.
  • Naldurg, Prasad
  • Narasimhan, Giri
  • Natarajan, Sivaramakrishnan R.
  • Novotný, Petr
  • Nowotka, Dirk
  • Panolan, Fahad
  • Peschanski, Frédéric
  • Philip, Geevarghese
  • Pinchinat, Sophie
  • Place, Thomas
  • Potapov, Igor
  • Rafiey, Arash
  • Raghavendra, K. R.
  • Rai, Ashutosh
  • Rajendraprasad, Deepak
  • Ramanujan, M. S.
  • Ramyaa, Ramyaa
  • Repke, Stefan
  • Roy, Sambuddha
  • Sabharwal, Yogish
  • Saha, Barna
  • Salvati, Sylvain
  • Saurabh, Saket
  • Schallhart, Christian
  • Schmid, Markus L.
  • Schwoon, Stefan
  • Serre, Olivier
  • Seth, Anil
  • Siebertz, Sebastian
  • Simaitis, Aistis
  • Smith, Tim
  • Srinivasan, Srikanth
  • Stamoulis, Georgios
  • Stefanescu, Alin
  • Suresh, S. P.
  • Sviridenko, Maxim
  • Tautschnig, Michael
  • Terui, Kazushige
  • Totzke, Patrick
  • van Rooijen, Lorijn
  • Veith, Helmut
  • Venkatasubramanian, Suresh
  • Villanger, Yngve
  • Vishnoi, Nisheeth K.
  • Walukiewicz, Igor
  • Zeitoun, Marc
  • Zhang, Zeyu
    		•

    		  
    Frontmatter, Table of Contents, Preface, Conference Organization
    Authors: Seth, Anil ; Vishnoi, Nisheeth K.

    Abstract | Document (362 KB) | BibTeX

    Polar Codes: Reliable Communication with Complexity Polynomial in the Gap to Shannon Capacity (Invited Talk)
    Authors: Guruswami, Venkatesan

    Abstract | Document (225 KB) | BibTeX

    Computing With a Fixed Number of Pointers (Invited Talk)
    Authors: Hofmann, Martin ; Ramyaa, Ramyaa

    Abstract | Document (623 KB) | BibTeX

    On Approximation Resistance of Predicates (Invited Talk)
    Authors: Khot, Subhash

    Abstract | Document (214 KB) | BibTeX

    Characterisations of Nowhere Dense Graphs (Invited Talk)
    Authors: Grohe, Martin ; Kreutzer, Stephan ; Siebertz, Sebastian

    Abstract | Document (523 KB) | BibTeX

    Intersection Types for Normalization and Verification (Invited Talk)
    Authors: Terui, Kazushige

    Abstract | Document (253 KB) | BibTeX

    Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound
    Authors: Crowston, Robert ; Jones, Mark ; Muciaccia, Gabriele ; Philip, Geevarghese ; Rai, Ashutosh ; Saurabh, Saket

    Abstract | Document (598 KB) | BibTeX

    On the Parameterised Complexity of String Morphism Problems
    Authors: Fernau, Henning ; Schmid, Markus L. ; Villanger, Yngve

    Abstract | Document (542 KB) | BibTeX

    Partially Polynomial Kernels for Set Cover and Test Cover
    Authors: Basavaraju, Manu ; Francis, Mathew C. ; Ramanujan, M. S. ; Saurabh, Saket

    Abstract | Document (539 KB) | BibTeX

    Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs
    Authors: Chitnis, Rajesh ; Fomin, Fedor V. ; Golovach, Petr A.

    Abstract | Document (462 KB) | BibTeX

    Böhm Trees as Higher-Order Recursive Schemes
    Authors: Clairambault, Pierre ; Murawski, Andrzej S.

    Abstract | Document (629 KB) | BibTeX

    Evaluation is MSOL-compatible
    Authors: Salvati, Sylvain ; Walukiewicz, Igor

    Abstract | Document (940 KB) | BibTeX

    Model Checking and Functional Program Transformations
    Authors: Haddad, Axel

    Abstract | Document (512 KB) | BibTeX

    A Theory of Partitioned Global Address Spaces
    Authors: Calin, Georgel ; Derevenetc, Egor ; Majumdar, Rupak ; Meyer, Roland

    Abstract | Document (706 KB) | BibTeX

    A Strong Direct Product Theorem for the Tribes Function via the Smooth-Rectangle Bound
    Authors: Harsha, Prahladh ; Jain, Rahul

    Abstract | Document (541 KB) | BibTeX

    Inapproximability of Rainbow Colouring
    Authors: Chandran, L. Sunil ; Rajendraprasad, Deepak

    Abstract | Document (434 KB) | BibTeX

    Primal Infon Logic: Derivability in Polynomial Time
    Authors: Baskar, Anguraj ; Naldurg, Prasad ; Raghavendra, K. R. ; Suresh, S. P.

    Abstract | Document (569 KB) | BibTeX

    Composition Problems for Braids
    Authors: Potapov, Igor

    Abstract | Document (560 KB) | BibTeX

    DLOGTIME Proof Systems
    Authors: Krebs, Andreas ; Limaye, Nutan

    Abstract | Document (456 KB) | BibTeX

    On Improved Degree Lower Bounds for Polynomial Approximation
    Authors: Srinivasan, Srikanth

    Abstract | Document (507 KB) | BibTeX

    Implementing Realistic Asynchronous Automata
    Authors: Akshay, S. ; Dinca, Ionut ; Genest, Blaise ; Stefanescu, Alin

    Abstract | Document (583 KB) | BibTeX

    Computation of Summaries Using Net Unfoldings
    Authors: Esparza, Javier ; Jezequel, Loig ; Schwoon, Stefan

    Abstract | Document (593 KB) | BibTeX

    Faster Deterministic Algorithms for r-Dimensional Matching Using Representative Sets
    Authors: Goyal, Prachi ; Misra, Neeldhara ; Panolan, Fahad

    Abstract | Document (525 KB) | BibTeX

    Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers
    Authors: Agarwal, Archita ; Chakaravarthy, Venkatesan T. ; Choudhury, Anamitra Roy ; Roy, Sambuddha ; Sabharwal, Yogish

    Abstract | Document (477 KB) | BibTeX

    Replica Placement via Capacitated Vertex Cover
    Authors: Arora, Sonika ; Chakaravarthy, Venkatesan T. ; Gupta, Neelima ; Mukherjee, Koyel ; Sabharwal, Yogish

    Abstract | Document (459 KB) | BibTeX

    Knapsack Cover Subject to a Matroid Constraint
    Authors: Chakaravarthy, Venkatesan T. ; Choudhury, Anamitra Roy ; Natarajan, Sivaramakrishnan R. ; Roy, Sambuddha

    Abstract | Document (386 KB) | BibTeX

    Jumping Automata for Uniform Strategies
    Authors: Maubert, Bastien ; Pinchinat, Sophie

    Abstract | Document (514 KB) | BibTeX

    Emptiness Of Alternating Tree Automata Using Games With Imperfect Information
    Authors: Fijalkow, Nathanaël ; Pinchinat, Sophie ; Serre, Olivier

    Abstract | Document (520 KB) | BibTeX

    Saturation of Concurrent Collapsible Pushdown Systems
    Authors: Hague, Matthew

    Abstract | Document (680 KB) | BibTeX

    Decidability Results on the Existence of Lookahead Delegators for NFA
    Authors: Löding, Christof ; Repke, Stefan

    Abstract | Document (487 KB) | BibTeX

    Fair Matchings and Related Problems
    Authors: Huang, Chien-Chung ; Kavitha, Telikepalli ; Mehlhorn, Kurt ; Michail, Dimitrios

    Abstract | Document (528 KB) | BibTeX

    Ranking with Diverse Intents and Correlated Contents
    Authors: Li, Jian ; Zhang, Zeyu

    Abstract | Document (545 KB) | BibTeX

    Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages
    Authors: Place, Thomas ; van Rooijen, Lorijn ; Zeitoun, Marc

    Abstract | Document (452 KB) | BibTeX

    On the Structure and Complexity of Rational Sets of Regular Languages
    Authors: Holzer, Andreas ; Schallhart, Christian ; Tautschnig, Michael ; Veith, Helmut

    Abstract | Document (578 KB) | BibTeX

    Geometric Avatar Problems
    Authors: Consuegra, Mario E. ; Narasimhan, Giri

    Abstract | Document (521 KB) | BibTeX

    Clustering With Center Constraints
    Authors: Chalermsook, Parinya ; Venkatasubramanian, Suresh

    Abstract | Document (479 KB) | BibTeX

    On Infinite Words Determined by Stack Automata
    Authors: Smith, Tim

    Abstract | Document (451 KB) | BibTeX

    The Combinatorics of Non-determinism
    Authors: Bodini, Olivier ; Genitrini, Antoine ; Peschanski, Frédéric

    Abstract | Document (528 KB) | BibTeX

    Renting a Cloud
    Authors: Saha, Barna

    Abstract | Document (441 KB) | BibTeX

    Energy Efficient Scheduling and Routing via Randomized Rounding
    Authors: Bampis, Evripidis ; Kononov, Alexander ; Letsios, Dimitrios ; Lucarelli, Giorgio ; Sviridenko, Maxim

    Abstract | Document (444 KB) | BibTeX

    PTAS for Ordered Instances of Resource Allocation Problems
    Authors: Khodamoradi, Kamyar ; Krishnamurti, Ramesh ; Rafiey, Arash ; Stamoulis, Georgios

    Abstract | Document (565 KB) | BibTeX

    On the Pseudoperiodic Extension of u^l = v^m w^n
    Authors: Manea, Florin ; Müller, Mike ; Nowotka, Dirk

    Abstract | Document (519 KB) | BibTeX

    Solvency Markov Decision Processes with Interest
    Authors: Brázdil, Tomás ; Chen, Taolue ; Forejt, Vojtech ; Novotný, Petr ; Simaitis, Aistis

    Abstract | Document (502 KB) | BibTeX

    Parameterized Verification of Many Identical Probabilistic Timed Processes
    Authors: Bertrand, Nathalie ; Fournier, Paulin

    Abstract | Document (512 KB) | BibTeX

    Simulation Over One-counter Nets is PSPACE-Complete
    Authors: Hofman, Piotr ; Lasota, Slawomir ; Mayr, Richard ; Totzke, Patrick

    Abstract | Document (529 KB) | BibTeX

    Optimal Constructions for Active Diagnosis
    Authors: Haar, Stefan ; Haddad, Serge ; Melliti, Tarek ; Schwoon, Stefan

    Abstract | Document (521 KB) | BibTeX

    		  



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