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.
Venues: Auditorium, Seminar Hall and Lecture Hall 06. See http://fsttcs2016.cmi.ac.in.
| 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 | |