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

Venues: Auditorium, Seminar Hall and Lecture Hall 06. See

13 December, 2016
1100 – 1200 Registration
Invited Talk 1
CHAIR: Jaikumar Radhakrishnan
1200 – 1300 Mikkel Thorup
Fast and Powerful Hashing using Tabulation
1300 – 1430 Lunch
Session 1A
CHAIR: Meena Mahajan
Session 1B
CHAIR: M. Praveen
1430 – 1500 Prahladh Harsha and Srikanth Srinivasan
Robust Multiplication-based Tests for Reed-Muller Codes
Anindya Banerjee, David Naumann and Mohammad Nikouei
Relational logic with framing and hypotheses
1500 – 1530 Aounon Kumar
Capacitated k-Center Problem with Vertex Weights
Vrunda Dave, Krishna S. and Ashutosh Trivedi
FO-definable transformations of infinite strings
1530 – 1600 Aritra Banik, Fahad Panolan, Venkatesh Raman and Vibha Sahlot
Frechet Distance Between a Line and Avatar Point Set
Emmanuel Filiot, Olivier Gauwin and Nathan Lhote
Aperiodicity of rational functions is PSpace-complete
1600 – 1630 Jaikumar Radhakrishnan and Swagato Sanyal
The zero-error randomized query complexity of the pointer function
Bartek Klin, Slawomir Lasota, Joanna Ochremiak and Szymon Torunczyk
Homomorphism problems for first-order definable structures
1630 – 1700 Coffee Break
Invited Talk 2
CHAIR: Madhavan Mukund
1700 – 1800 Tevfik Bultan
Side Channel Analysis Using a Model Counting Constraint Solver and Symbolic Execution
1800 – 1830 Coffee Break
14 December, 2016
Invited Talk 3
CHAIR: Sandeep Sen
0900 – 1000 Aleksander Madry
Continuous Optimization: The "Right" Language for Graph Algorithms?
1000 – 1030 Coffee break
Session 2A
CHAIR: G Philip
Session 2B
CHAIR: Slawomir Lasota
1030 – 1100 Ashutosh Rai and Ramanujan M. S.
Strong Parameterized Deletion: Bipartite Graphs
Moses Ganardi, Danny Hucke and Markus Lohrey
Querying regular languages over sliding-windows
1100 – 1130 Fahad Panolan and Meirav Zehavi
Parameterized Algorithms for List K-Cycle
Xuan Bach Le, Aquinas Hobor and Anthony W. Lin
Decidability and Complexity of Tree Share Formulas
1130 – 1200 R Krithika, Pranabendu Misra, Ashutosh Rai and Prafullkumar Tale
Lossy Kernels for Graph Contraction Problems
Benedikt Bollig
One-Counter Automata with Counter Observability
1200 – 1230 Mithilesh Kumar and Daniel Lokshtanov
Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments
1230 – 1400 Lunch
Invited Talk 4
CHAIR: S. Akshay
1400 – 1500 Holger Hermanns
My O is bigger than yours
1500 – 1510 Short Break
Session 4A1 (Auditorium)
CHAIR: Mark de Berg
Session 4A2 (Lecture Hall 6)
CHAIR: Venkatesh Raman
Session 3B (Seminar Hall)
CHAIR: Sophie Pinchinat
1510 – 1540 Sushmita Gupta and Sanjukta Roy
Stable Matching Games : Manipulation via Subgraph Isomorphism
Nirman Kumar, Benjamin Raichel, Subhash Suri and Kevin Verbeek
Most Likely Voronoi Diagrams in Higher Dimensions
Laura Bozzelli, Alberto Molinari, Angelo Montanari, Adriano Peron and Pietro Sala
Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison
1540 – 1610 Umang Bhaskar, Ajil Jalal and Rahul Vaze
The Adwords Problem with Strict Capacity Constraints
Javier Esparza, Pierre Ganty, Jerome Leroux and Rupak Majumdar
Model Checking Population Protocols
1610 – 1640 Coffee Break
Session 5A1 (Auditorium)
CHAIR: Fahad Panolan
Session 5A2 (Lecture Hall 6)
CHAIR: Venkatesh Raman
Session 3B Contd. (Seminar Hall)
CHAIR: Sophie Pinchinat
1640 – 1710 Ankit Chauhan, Tobias Friedrich and Ralf Rothenberger
Greed is Good for Deterministic Scale-Free Networks
Pawel Gawrychowski and Artur Jez
LZ77 factorisation of trees
Alexander Weinert and Martin Zimmermann
Visibly Linear Dynamic Logic
1710 – 1740 Mark de Berg, Bart M. P. Jansen and Debankur Mukherjee
Independent Set Reconfiguration Thresholds of Hereditary Graph Classes
Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording and Inge Li Gortz
Finger Search in Grammar-Compressed Strings
Bingtian Xue, Kim Guldstrand Larsen and Radu Mardare
Probabilistic Mu-Calculus: Decidability and Complete Axiomatization
1745 – 1830 IARCS Business Meeting
1900 – 2200 Conference Banquet (Venue: Gokulam Park Sabari)
15 December, 2016
Invited Talk 5
CHAIR: M. S. Ramanujan
0900 – 1000 Fedor Fomin
Graph decompositions and algorithms
1000 – 1030 Coffee break
Session 6A (Auditorium)
CHAIR: Umang Bhaskar
Session 6B (Seminar Hall)
CHAIR: B. Srivathsan
Session 6C (Lecture Hall 06)
CHAIR: Saket Saurabh
1030 – 1100 Krishnammorthy Dinesh, Sajin Koroth and Jayalal Sarma
Characterization and Lower Bounds for Branching Program Size using Projective Dimension
Sebastian Muskalla, Roland Meyer and Lukas Holik
Summaries for Context-Free Games
Karthik C. S. and Sebastien Tavenas
On the Sensitivity Conjecture for Disjunctive Normal Forms
1100 – 1130 Mrinal Kumar and Ramprasad Saptharishi
Finer separations between shallow arithmetic circuits
Romain Brenguier, Guillermo Perez, Jean-Francois Raskin and Ocan Sankur
Admissibility in Quantitative Graph Games
Sanjoy Baruah, Zhishan Guo and Arvind Easwaran
Mixed-criticality scheduling to minimize makespan
1130 – 1200 C Ramya and Raghavendra Rao B V
Sum of products of Read Once Polynomials
Felix Klein and Martin Zimmermann
Prompt Delay
Waldo Galvez, Fabrizio Grandoni, Salvatore Ingala and Arindam Khan
Improved Pseudo-Polynomial-Time Approximation for Strip Packing
1200 – 1230 Olaf Beyersdorff, Leroy Chew, Meena Mahajan and Anil Shukla
Understanding Cutting Planes for QBFs
Shibashis Guha, Marcin Jurdzinski, Krishna S. and Ashutosh Trivedi
Mean-Payoff Games on Timed Automata
Amit Deshpande, Prahladh Harsha and Rakesh Venkat
Embedding Approximately Low Dimensional l_2-squared metrics into l1
1230 – 1400 Lunch
Invited Talk 6
CHAIR: Akash Lal
1400 – 1500 Mooly Sagiv
Simple invariants for proving the safety of distributed protocols
1500 – 1530 Coffee Break
Session 7A (Auditorium)
CHAIR: Jaikumar Radhakrishnan
Session 7B (Seminar Hall)
CHAIR: Mooly Sagiv
1530 – 1600 Piotr Berman, Meiram Murzabulatov and Sofya Raskhodnikova
The Power and Limitations of Uniform Samples in Testing Properties of Figures
Frederic Herbreteau, B Srivathsan, Thanh-Tung Tran and Igor Walukiewicz
Why liveness for timed automata is hard, and what we can do about it
1600 – 1630 Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota and Elena Grigorescu
Local Testing for Membership in Lattices
Maximilian Paul Louis Haslbeck and Tobias Nipkow
Verified Analysis of List Update Algorithms
1630 – 1700 Sriram V. Pemmaraju and Vivek B. Sardeshmukh
Super-fast MST Algorithms in the Congested Clique using o(m) Messages
Jaroslav Bendik, Nikola Benes, Ivana Cerna and Jiri Barnat
Tunable Online MUS/MSS Enumeration
1705 – 1710 Closing Remarks