FSTTCS 2016
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Chennai Mathematical Institute, Chennai. December 13–15, 2016.
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 fsttcs2016@cmi.ac.in.
Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording and Inge Li Gørtz
Finger Search in Grammar-Compressed Strings
Bingtian Xue, Kim Guldstrand Larsen and Radu Mardare
Probabilistic Mu-Calculus: Decidability and Complete Axiomatization
Sanjoy Baruah, Zhishan Guo and Arvind Easwaran
Mixed-criticality scheduling to minimize makespan
Fahad Panolan and Meirav Zehavi
Parameterized Algorithms for List K-Cycle
Benedikt Bollig.
One-Counter Automata with Counter Observability
Laura Bozzelli, Alberto Molinari, Angelo Montanari, Adriano Peron and Pietro Sala
Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison
Piotr Berman, Meiram Murzabulatov and Sofya Raskhodnikova
The Power and Limitations of Uniform Samples in Testing Properties of Figures
Olaf Beyersdorff, Leroy Chew, Meena Mahajan and Anil Shukla
Understanding Cutting Planes for QBFs
Krishnammorthy Dinesh, Sajin Koroth and Jayalal Sarma
Characterization and Lower Bounds for Branching Program Size using Projective Dimension
Mrinal Kumar and Ramprasad Saptharishi
Finer separations between shallow arithmetic circuits
Bartek Klin, Sławomir Lasota, Joanna Ochremiak and Szymon Toruńczyk
Homomorphism problems for first-order definable structures
Alexander Weinert and Martin Zimmermann
Visibly Linear Dynamic Logic
Emmanuel Filiot, Olivier Gauwin and Nathan Lhote
Aperiodicity of rational functions is PSpace-complete
C Ramya and Raghavendra Rao B V
Sum of products of Read Once Polynomials
Jaikumar Radhakrishnan and Swagato Sanyal
The zero-error randomized query complexity of the pointer function.
Romain Brenguier, Guillermo Perez, Jean-Francois Raskin and Ocan Sankur
Admissibility in Quantitative Graph Games
Maximilian Paul Louis Haslbeck and Tobias Nipkow
Verified Analysis of List Update Algorithms
Felix Klein and Martin Zimmermann
Prompt Delay
Jaroslav Bendík, Nikola Benes, Ivana Cerna and Jiri Barnat
Tunable Online MUS/MSS Enumeration
Moses Ganardi, Danny Hucke and Markus Lohrey
Querying regular languages over sliding-windows
Umang Bhaskar, Ajil Jalal and Rahul Vaze
The Adwords Problem with Strict Capacity Constraints
Karthik C. S. and Sébastien Tavenas
On the Sensitivity Conjecture for Disjunctive Normal Forms
Aounon Kumar.
Capacitated k-Center Problem with Vertex Weights
Pawel Gawrychowski and Artur Jeż
LZ77 factorisation of trees
R Krithika, Pranabendu Misra, Ashutosh Rai and Prafullkumar Tale
Lossy Kernels for Graph Contraction Problems
Mark de Berg, Bart M. P. Jansen and Debankur Mukherjee
Independent Set Reconfiguration Thresholds of Hereditary Graph Classes
Amit Deshpande, Prahladh Harsha and Rakesh Venkat
Embedding Approximately Low Dimensional l_2-squared metrics into l1
Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala and Arindam Khan
Improved Pseudo-Polynomial-Time Approximation for Strip Packing
Javier Esparza, Pierre Ganty, Jérôme Leroux and Rupak Majumdar
Model Checking Population Protocols
Ashutosh Rai and Ramanujan M. S.
Strong Parameterized Deletion: Bipartite Graphs
Shibashis Guha, Marcin Jurdziński, Krishna S. and Ashutosh Trivedi
Mean-Payoff Games on Timed Automata
Aritra Banik, Fahad Panolan, Venkatesh Raman and Vibha Sahlot
Frechet Distance Between a Line and Avatar Point Set
Ankit Chauhan, Tobias Friedrich and Ralf Rothenberger
Greed is Good for Deterministic Scale-Free Networks
Sushmita Gupta and Sanjukta Roy
Stable Matching Games : Manipulation via Subgraph Isomorphism
Anindya Banerjee, David Naumann and Mohammad Nikouei
Relational logic with framing and hypotheses
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
Nirman Kumar, Benjamin Raichel, Subhash Suri and Kevin Verbeek
Most Likely Voronoi Diagrams in Higher Dimensions
Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota and Elena Grigorescu
Local Testing for Membership in Lattices
Sriram V. Pemmaraju and Vivek B. Sardeshmukh
Super-fast MST Algorithms in the Congested Clique using o(m) Messages
Xuan Bach Le, Aquinas Hobor and Anthony W. Lin
Decidability and Complexity of Tree Share Formulas
Prahladh Harsha and Srikanth Srinivasan
Robust Multiplication-based Tests for Reed-Muller Codes
Vrunda Dave, Krishna S. and Ashutosh Trivedi
FO-definable transformations of infinite strings
Sebastian Muskalla, Roland Meyer and Lukas Holik
Summaries for Context-Free Games
Mithilesh Kumar and Daniel Lokshtanov
Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments