Skip to main content


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

Chennai Mathematical Institute, Chennai. December 13–15, 2016.

Click here for the online FSTTCS'16 proceedings.
Online registration for FSTTCS 2016 is closed. If you wish to register, please send an email to

  1. Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording and Inge Li Gørtz
    Finger Search in Grammar-Compressed Strings

  2. Bingtian Xue, Kim Guldstrand Larsen and Radu Mardare
    Probabilistic Mu-Calculus: Decidability and Complete Axiomatization

  3. Sanjoy Baruah, Zhishan Guo and Arvind Easwaran
    Mixed-criticality scheduling to minimize makespan

  4. Fahad Panolan and Meirav Zehavi
    Parameterized Algorithms for List K-Cycle

  5. Benedikt Bollig.
    One-Counter Automata with Counter Observability

  6. Laura Bozzelli, Alberto Molinari, Angelo Montanari, Adriano Peron and Pietro Sala
    Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison

  7. Piotr Berman, Meiram Murzabulatov and Sofya Raskhodnikova
    The Power and Limitations of Uniform Samples in Testing Properties of Figures

  8. Olaf Beyersdorff, Leroy Chew, Meena Mahajan and Anil Shukla
    Understanding Cutting Planes for QBFs

  9. Krishnammorthy Dinesh, Sajin Koroth and Jayalal Sarma
    Characterization and Lower Bounds for Branching Program Size using Projective Dimension

  10. Mrinal Kumar and Ramprasad Saptharishi
    Finer separations between shallow arithmetic circuits

  11. Bartek Klin, Sławomir Lasota, Joanna Ochremiak and Szymon Toruńczyk
    Homomorphism problems for first-order definable structures

  12. Alexander Weinert and Martin Zimmermann
    Visibly Linear Dynamic Logic

  13. Emmanuel Filiot, Olivier Gauwin and Nathan Lhote
    Aperiodicity of rational functions is PSpace-complete

  14. C Ramya and Raghavendra Rao B V
    Sum of products of Read Once Polynomials

  15. Jaikumar Radhakrishnan and Swagato Sanyal
    The zero-error randomized query complexity of the pointer function.

  16. Romain Brenguier, Guillermo Perez, Jean-Francois Raskin and Ocan Sankur
    Admissibility in Quantitative Graph Games

  17. Maximilian Paul Louis Haslbeck and Tobias Nipkow
    Verified Analysis of List Update Algorithms

  18. Felix Klein and Martin Zimmermann
    Prompt Delay

  19. Jaroslav Bendík, Nikola Benes, Ivana Cerna and Jiri Barnat
    Tunable Online MUS/MSS Enumeration

  20. Moses Ganardi, Danny Hucke and Markus Lohrey
    Querying regular languages over sliding-windows

  21. Umang Bhaskar, Ajil Jalal and Rahul Vaze
    The Adwords Problem with Strict Capacity Constraints

  22. Karthik C. S. and Sébastien Tavenas
    On the Sensitivity Conjecture for Disjunctive Normal Forms

  23. Aounon Kumar.
    Capacitated k-Center Problem with Vertex Weights

  24. Pawel Gawrychowski and Artur Jeż
    LZ77 factorisation of trees

  25. R Krithika, Pranabendu Misra, Ashutosh Rai and Prafullkumar Tale
    Lossy Kernels for Graph Contraction Problems

  26. Mark de Berg, Bart M. P. Jansen and Debankur Mukherjee
    Independent Set Reconfiguration Thresholds of Hereditary Graph Classes

  27. Amit Deshpande, Prahladh Harsha and Rakesh Venkat
    Embedding Approximately Low Dimensional l_2-squared metrics into l1

  28. Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala and Arindam Khan
    Improved Pseudo-Polynomial-Time Approximation for Strip Packing

  29. Javier Esparza, Pierre Ganty, Jérôme Leroux and Rupak Majumdar
    Model Checking Population Protocols

  30. Ashutosh Rai and Ramanujan M. S.
    Strong Parameterized Deletion: Bipartite Graphs

  31. Shibashis Guha, Marcin Jurdziński, Krishna S. and Ashutosh Trivedi
    Mean-Payoff Games on Timed Automata

  32. Aritra Banik, Fahad Panolan, Venkatesh Raman and Vibha Sahlot
    Frechet Distance Between a Line and Avatar Point Set

  33. Ankit Chauhan, Tobias Friedrich and Ralf Rothenberger
    Greed is Good for Deterministic Scale-Free Networks

  34. Sushmita Gupta and Sanjukta Roy
    Stable Matching Games : Manipulation via Subgraph Isomorphism

  35. Anindya Banerjee, David Naumann and Mohammad Nikouei
    Relational logic with framing and hypotheses

  36. Frédéric Herbreteau, B Srivathsan, Thanh-Tung Tran and Igor Walukiewicz
    Why liveness for timed automata is hard, and what we can do about it

  37. Nirman Kumar, Benjamin Raichel, Subhash Suri and Kevin Verbeek
    Most Likely Voronoi Diagrams in Higher Dimensions

  38. Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota and Elena Grigorescu
    Local Testing for Membership in Lattices

  39. Sriram V. Pemmaraju and Vivek B. Sardeshmukh
    Super-fast MST Algorithms in the Congested Clique using o(m) Messages

  40. Xuan Bach Le, Aquinas Hobor and Anthony W. Lin
    Decidability and Complexity of Tree Share Formulas

  41. Prahladh Harsha and Srikanth Srinivasan
    Robust Multiplication-based Tests for Reed-Muller Codes

  42. Vrunda Dave, Krishna S. and Ashutosh Trivedi
    FO-definable transformations of infinite strings

  43. Sebastian Muskalla, Roland Meyer and Lukas Holik
    Summaries for Context-Free Games

  44. Mithilesh Kumar and Daniel Lokshtanov
    Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments