36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science FSTTCS 2016, December 13–15, 2016, Chennai, India Edited by Akash Lal S. Akshay Saket Saurabh Sandeep Sen LIPIcs – Vol. 65 – FSTTCS 2016 www.dagstuhl.de/lipics Editors Akash Lal S. Akshay MSR India IIT Bombay Bangalore 560001 Mumbai 76 India India [email protected] [email protected] Saket Saurabh Sandeep Sen IMSc Chennai IIT Delhi Chennai Delhi India India [email protected] [email protected] ACM Classification 1998 D.2.4 Software/Program Verification, F.1.1 Models of Computation, F.1.2 Modes of Computation, F.1.3 Complexity Measures and Classes, F.2.2 Nonnumerical Algorithms and Problems, F.3.1 Specifying and Verifying and Reasoning about Programs, F.4.1 Mathematical Logic, F.4.3 Formal Languages ISBN 978-3-95977-027-9 Published online and open access by Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, Saarbrücken/Wadern, Germany. Online available at http://www.dagstuhl.de/dagpub/978-3-95977-027-9. Publication date December, 2016 Bibliographic information published by the Deutsche Nationalbibliothek The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data are available in the Internet at http://dnb.d-nb.de. License This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC-BY 3.0): http://creativecommons.org/licenses/by/3.0/legalcode. In brief, this license authorizes each and everybody to share (to copy, distribute and transmit) the work under the following conditions, without impairing or restricting the authors’ moral rights: Attribution: The work must be attributed to its authors. The copyright is retained by the corresponding authors. Digital Object Identifier: 10.4230/LIPIcs.FSTTCS.2016.0 ISBN 978-3-95977-027-9 ISSN 1868-8969 http://www.dagstuhl.de/lipics 0:iii LIPIcs – Leibniz International Proceedings in Informatics LIPIcs is a series of high-quality conference proceedings across all fields in informatics. LIPIcs volumes are published according to the principle of Open Access, i.e., they are available online and free of charge. Editorial Board Susanne Albers (TU München) Chris Hankin (Imperial College London) Deepak Kapur (University of New Mexico) Michael Mitzenmacher (Harvard University) Madhavan Mukund (Chennai Mathematical Institute) Catuscia Palamidessi (INRIA) Wolfgang Thomas (Chair, RWTH Aachen) Pascal Weil (CNRS and University Bordeaux) Reinhard Wilhelm (Saarland University) ISSN 1868-8969 http://www.dagstuhl.de/lipics FSTTCS 2016 Contents Preface Akash Lal, S. Akshay, Saket Saurabh and Sandeep Sen ........................... ix Conference Organization ................................................................................. xi External Reviewers ................................................................................. xiii Invited Talks Fast and Powerful Hashing Using Tabulation Mikkel Thorup ................................................................... 1:1–1:2 Simple Invariants for Proving the Safety of Distributed Protocols Mooly Sagiv ..................................................................... 2:1–2:1 My O Is Bigger Than Yours Holger Hermanns ................................................................ 3:1–3:2 Continuous Optimization: The “Right” Language for Graph Algorithms? Aleksander Mądry ............................................................... 4:1–4:2 Graph Decompositions and Algorithms Fedor V. Fomin ................................................................. 5:1–5:1 Side Channel Analysis Using a Model Counting Constraint Solver and Symbolic Execution Tevfik Bultan .................................................................... 6:1–6:2 Contributed Papers Session 1A Mixed-Criticality Scheduling to Minimize Makespan Sanjoy Baruah, Arvind Easwaran, and Zhishan Guo ............................. 7:1–7:13 Capacitated k-Center Problem with Vertex Weights Aounon Kumar .................................................................. 8:1–8:14 Improved Pseudo-Polynomial-Time Approximation for Strip Packing Waldo Gálvez, Fabrizio Grandoni, Salvatore Ingala, and Arindam Khan .......... 9:1–9:14 Embedding Approximately Low-Dimensional ‘2 Metrics into ‘ 2 1 Amit Deshpande, Prahladh Harsha, and Rakesh Venkat .......................... 10:1–10:13 Session 1B Relational Logic with Framing and Hypotheses Anindya Banerjee, David A. Naumann, and Mohammad Nikouei ................. 11:1–11:16 36th IARCS Annual Conference on Foundations of SoftwareTechnology and Theoretical Computer Science (FSTTCS2016). Editors: AkashLal,S.Akshay,SaketSaurabh,andSandeepSen LeibnizInternationalProceedingsinInformatics SchlossDagstuhl–Leibniz-ZentrumfürInformatik,DagstuhlPublishing,Germany 0:vi Contents FO-Definable Transformations of Infinite Strings Vrunda Dave, Shankara Narayanan Krishna, and Ashutosh Trivedi ............... 12:1–12:14 Aperiodicity of Rational Functions Is PSPACE-Complete Emmanuel Filiot, Olivier Gauwin, and Nathan Lhote ............................ 13:1–13:15 Homomorphism Problems for First-Order Definable Structures Bartek Klin, Sławomir Lasota, Joanna Ochremiak, and Szymon Toruńczyk ....... 14:1–14:15 Session 2A On the Sensitivity Conjecture for Disjunctive Normal Forms Karthik C.S. and Sébastien Tavenas ............................................. 15:1–15:15 The Zero-Error Randomized Query Complexity of the Pointer Function Jaikumar Radhakrishnan and Swagato Sanyal .................................... 16:1–16:13 Robust Multiplication-Based Tests for Reed-Muller Codes Prahladh Harsha and Srikanth Srinivasan ........................................ 17:1–17:14 Session 2B Querying Regular Languages over Sliding Windows Moses Ganardi, Danny Hucke, and Markus Lohrey ............................... 18:1–18:14 Decidability and Complexity of Tree Share Formulas Xuan Bach Le, Aquinas Hobor, and Anthony W. Lin ............................ 19:1–19:14 One-Counter Automata with Counter Observability Benedikt Bollig .................................................................. 20:1–20:14 Session 3A Strong Parameterized Deletion: Bipartite Graphs Ashutosh Rai and M.S. Ramanujan .............................................. 21:1–21:14 Parameterized Algorithms for List K-Cycle Fahad Panolan and Meirav Zehavi ............................................... 22:1–22:15 Lossy Kernels for Graph Contraction Problems R. Krithika, Pranabendu Misra, Ashutosh Rai, and Prafullkumar Tale ............ 23:1–23:14 Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments Mithilesh Kumar and Daniel Lokshtanov ......................................... 24:1–24:15 Session 3B Probabilistic Mu-Calculus: Decidability and Complete Axiomatization Kim G. Larsen, Radu Mardare, and Bingtian Xue ............................... 25:1–25:18 Contents 0:vii Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison Laura Bozzelli, Alberto Molinari, Angelo Montanari, Adriano Peron, and Pietro Sala .................................................................. 26:1–26:14 Model Checking Population Protocols Javier Esparza, Pierre Ganty, Jérôme Leroux, and Rupak Majumdar ............. 27:1–27:14 Visibly Linear Dynamic Logic Alexander Weinert and Martin Zimmermann .................................... 28:1–28:14 Session 4A1 Stable Matching Games: Manipulation via Subgraph Isomorphism Sushmita Gupta and Sanjukta Roy ............................................... 29:1–29:14 The Adwords Problem with Strict Capacity Constraints Umang Bhaskar, Ajil Jalal, and Rahul Vaze ...................................... 30:1–30:14 Session 4A2 Most Likely Voronoi Diagrams in Higher Dimensions Nirman Kumar, Benjamin Raichel, Subhash Suri, and Kevin Verbeek ............ 31:1–31:14 Fréchet Distance Between a Line and Avatar Point Set Aritra Banik, Fahad Panolan, Venkatesh Raman, and Vibha Sahlot .............. 32:1–32:14 Session 5A1 Greed is Good for Deterministic Scale-Free Networks Ankit Chauhan, Tobias Friedrich, and Ralf Rothenberger ......................... 33:1–33:15 Independent-Set Reconfiguration Thresholds of Hereditary Graph Classes Mark de Berg, Bart M.P. Jansen, and Debankur Mukherjee ..................... 34:1–34:15 Session 5A2 LZ77 Factorisation of Trees Paweł Gawrychowski and Artur Jeż .............................................. 35:1–35:15 Finger Search in Grammar-Compressed Strings Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording, and Inge Li Gørtz ............................................................... 36:1–36:16 Session 6A Characterization and Lower Bounds for Branching Program Size Using Projective Dimension Krishnamoorthy Dinesh, Sajin Koroth, and Jayalal Sarma ....................... 37:1–37:14 Finer Separations Between Shallow Arithmetic Circuits Mrinal Kumar and Ramprasad Saptharishi ....................................... 38:1–38:12 FSTTCS 2016 0:viii Contents Sum of Products of Read-Once Formulas Ramya C. and B.V. Raghavendra Rao ........................................... 39:1–39:15 Understanding Cutting Planes for QBFs Olaf Beyersdorff, Leroy Chew, Meena Mahajan, and Anil Shukla ................. 40:1–40:15 Session 6B Summaries for Context-Free Games Lukáš Holík, Roland Meyer, and Sebastian Muskalla ............................. 41:1–41:16 Admissibility in Quantitative Graph Games Romain Brenguier, Guillermo A. Pérez, Jean-François Raskin, and Ocan Sankur ................................................................ 42:1–42:14 Prompt Delay Felix Klein and Martin Zimmermann ............................................ 43:1–43:14 Mean-Payoff Games on Timed Automata Shibashis Guha, Marcin Jurdziński, Shankara Narayanan Krishna, and Ashutosh Trivedi ............................................................ 44:1–44:14 Session 7A The Power and Limitations of Uniform Samples in Testing Properties of Figures Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova .................. 45:1–45:14 Local Testing for Membership in Lattices Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, and Elena Grigorescu ............................................................ 46:1–46:14 Super-Fast MST Algorithms in the Congested Clique Using o(m) Messages Sriram V. Pemmaraju and Vivek B. Sardeshmukh ............................... 47:1–47:15 Session 7B Why Liveness for Timed Automata Is Hard, and What We Can Do About It Frédéric Herbreteau, B. Srivathsan, Thanh-Tung Tran, and Igor Walukiewicz ..... 48:1–48:14 Verified Analysis of List Update Algorithms Maximilian P.L. Haslbeck and Tobias Nipkow ................................... 49:1–49:15 Tunable Online MUS/MSS Enumeration Jaroslav Bendík, Nikola Beneš, Ivana Černá, and Jiří Barnat .................... 50:1–50:13 Preface The 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical ComputerScience(FSTTCS2016),organizedannuallybytheIndianAssociationforResearch in Computing Science (IARCS), was held at the Chennai Mathematical Institute, Chennai, from December 13 to December 15, 2016. The program consisted of 6 invited talks and 44 contributed papers. This proceedings volume contains the contributed papers and abstracts of invited talks presented at the conference. The proceedings of FSTTCS 2016 is published as a volume in the LIPIcs series under a Creative Commons license, with free online access to all, and with authors retaining rights over their contributions. The 44 contributed papers were selected from a total of 112 submissions. We thank the program committee for its efforts in carefully evaluating and making these selections. We thank all those who submitted their papers to FSTTCS 2016. We also thank the external reviewers for sending their informative and timely reviews. We are particularly grateful to the invited speakers: Tevfik Bultan (University of Califor- nia, Santa Barbara), Fedor V. Fomin (University of Bergen), Holger Hermanns (Saarland University), Aleksander Mądry (Massachusetts Institute of Technology), Mooly Sagiv (Tel Aviv University), and Mikkel Thorup (University of Copenhagen) who readily accepted our invitation to speak at the conference. There was one pre-conference workshop, Rangoli of Algorithms (RoA) and one post- conference workshop, Algorithmic Verification of Real-Time Systems (AVeRTS). We thank Fedor V. Fomin (University of Bergen), Krishna S. (IIT Bombay), Saket Saurabh (IMSc & University of Bergen), Roohani Sharma (IMSc), Ashutosh Trivedi (University of Colorado, Boulder), and Meirav Zehavi (University of Bergen), for organizing these workshops. On the administrative side, we thank the entire Computer Science Group, Chennai Mathematical Institute (CMI), who put in many months of effort in ensuring excellent conference and workshop arrangements at the Chennai Mathematical Institute. We would also like to thank G. Ramalingam, Madhavan Mukund, S.P. Suresh, Supratik Chakraborty and Venkatesh Raman for promptly responding to our numerous questions and requests relating to the organization of the conference. WealsothanktheEasychairteamwhosesoftwarehasmadeitveryconvenienttodomany conference related tasks. Finally, we thank the Dagstuhl LIPIcs staff for their coordination in the production of this proceedings, particularly Marc Herbstritt who was very prompt and helpful in answering our questions. Akash Lal, S. Akshay, Saket Saurabh and Sandeep Sen December 2016 36th IARCS Annual Conference on Foundations of SoftwareTechnology and Theoretical Computer Science (FSTTCS2016). Editors: AkashLal,S.Akshay,SaketSaurabh,andSandeepSen LeibnizInternationalProceedingsinInformatics SchlossDagstuhl–Leibniz-ZentrumfürInformatik,DagstuhlPublishing,Germany