FSTTCS 2016 December 13-15, 2016 - Chennai, India

36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)



Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen (Eds.)
ISBN 978-3-95977-027-9, LIPICS Vol. 65 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 24 MB)
Search Publication Server

Authors
  • Akshay, S.
  • Banerjee, Anindya
  • Banik, Aritra
  • Barnat, Jirí
  • Baruah, Sanjoy
  • Bendík, Jaroslav
  • Benes, Nikola
  • Berman, Piotr
  • Beyersdorff, Olaf
  • Bhaskar, Umang
  • Bille, Philip
  • Bollig, Benedikt
  • Bozzelli, Laura
  • Brenguier, Romain
  • Bultan, Tevfik
  • C., Ramya
  • Cerná, Ivana
  • Chandrasekaran, Karthekeyan
  • Chauhan, Ankit
  • Cheraghchi, Mahdi
  • Chew, Leroy
  • Christiansen, Anders Roy
  • Cording, Patrick Hagge
  • Dave, Vrunda
  • de Berg, Mark
  • Deshpande, Amit
  • Dinesh, Krishnamoorthy
  • Easwaran, Arvind
  • Esparza, Javier
  • Filiot, Emmanuel
  • Fomin, Fedor V.
  • Friedrich, Tobias
  • Ganardi, Moses
  • Gandikota, Venkata
  • Ganty, Pierre
  • Gauwin, Olivier
  • Gawrychowski, Pawel
  • Gortz, Inge Li
  • Grandoni, Fabrizio
  • Grigorescu, Elena
  • Guha, Shibashis
  • Guo, Zhishan
  • Gupta, Sushmita
  • Gálvez, Waldo
  • Harsha, Prahladh
  • Haslbeck, Maximilian P. L.
  • Herbreteau, Frédéric
  • Hermanns, Holger
  • Hobor, Aquinas
  • Holík, Lukás
  • Hucke, Danny
  • Ingala, Salvatore
  • Jalal, Ajil
  • Jansen, Bart M. P.
  • Jez, Artur
  • Jurdzinski, Marcin
  • Khan, Arindam
  • Klein, Felix
  • Klin, Bartek
  • Koroth, Sajin
  • Krishna, Shankara Narayanan
  • Krithika, R.
  • Kumar, Aounon
  • Kumar, Mithilesh
  • Kumar, Mrinal
  • Kumar, Nirman
  • Lal, Akash
  • Larsen, Kim G.
  • Lasota, Slawomir
  • Le, Xuan Bach
  • Leroux, Jérôme
  • Lhote, Nathan
  • Lin, Anthony W.
  • Lohrey, Markus
  • Lokshtanov, Daniel
  • Madry, Aleksander
  • Mahajan, Meena
  • Majumdar, Rupak
  • Mardare, Radu
  • Meyer, Roland
  • Misra, Pranabendu
  • Molinari, Alberto
  • Montanari, Angelo
  • Mukherjee, Debankur
  • Murzabulatov, Meiram
  • Muskalla, Sebastian
  • Naumann, David A.
  • Nikouei, Mohammad
  • Nipkow, Tobias
  • Ochremiak, Joanna
  • Panolan, Fahad
  • Pemmaraju, Sriram V.
  • Peron, Adriano
  • Pérez, Guillermo A.
  • Radhakrishnan, Jaikumar
  • Rai, Ashutosh
  • Raichel, Benjamin
  • Raman, Venkatesh
  • Ramanujan, M. S.
  • Rao, B. V. Raghavendra
  • Raskhodnikova, Sofya
  • Raskin, Jean-Francois
  • Rothenberger, Ralf
  • Roy, Sanjukta
  • S., Karthik C.
  • Sagiv, Mooly
  • Sahlot, Vibha
  • Sala, Pietro
  • Sankur, Ocan
  • Sanyal, Swagato
  • Saptharishi, Ramprasad
  • Sardeshmukh, Vivek B.
  • Sarma, Jayalal
  • Saurabh, Saket
  • Sen, Sandeep
  • Shukla, Anil
  • Srinivasan, Srikanth
  • Srivathsan, B.
  • Suri, Subhash
  • Tale, Prafullkumar
  • Tavenas, Sébastien
  • Thorup, Mikkel
  • Torunczyk, Szymon
  • Tran, Thanh-Tung
  • Trivedi, Ashutosh
  • Vaze, Rahul
  • Venkat, Rakesh
  • Verbeek, Kevin
  • Walukiewicz, Igor
  • Weinert, Alexander
  • Xue, Bingtian
  • Zehavi, Meirav
  • Zimmermann, Martin
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization, External Reviewers
    Authors: Lal, Akash ; Akshay, S. ; Saurabh, Saket ; Sen, Sandeep

    Abstract | Document (347 KB) | BibTeX

    Fast and Powerful Hashing Using Tabulation (Invited Talk)
    Authors: Thorup, Mikkel

    Abstract | Document (295 KB) | BibTeX

    Simple Invariants for Proving the Safety of Distributed Protocols (Invited Talk)
    Authors: Sagiv, Mooly

    Abstract | Document (236 KB) | BibTeX

    My O Is Bigger Than Yours (Invited Talk)
    Authors: Hermanns, Holger

    Abstract | Document (300 KB) | BibTeX

    Continuous Optimization: The “Right” Language for Graph Algorithms? (Invited Talk)
    Authors: Madry, Aleksander

    Abstract | Document (270 KB) | BibTeX

    Graph Decompositions and Algorithms (Invited Talk)
    Authors: Fomin, Fedor V.

    Abstract | Document (198 KB) | BibTeX

    Side Channel Analysis Using a Model Counting Constraint Solver and Symbolic Execution (Invited Talk)
    Authors: Bultan, Tevfik

    Abstract | Document (269 KB) | BibTeX

    Mixed-Criticality Scheduling to Minimize Makespan
    Authors: Baruah, Sanjoy ; Easwaran, Arvind ; Guo, Zhishan

    Abstract | Document (519 KB) | BibTeX

    Capacitated k-Center Problem with Vertex Weights
    Authors: Kumar, Aounon

    Abstract | Document (514 KB) | BibTeX

    Improved Pseudo-Polynomial-Time Approximation for Strip Packing
    Authors: Gálvez, Waldo ; Grandoni, Fabrizio ; Ingala, Salvatore ; Khan, Arindam

    Abstract | Document (617 KB) | BibTeX

    Embedding Approximately Low-Dimensional l_2^2 Metrics into l_1
    Authors: Deshpande, Amit ; Harsha, Prahladh ; Venkat, Rakesh

    Abstract | Document (480 KB) | BibTeX

    Relational Logic with Framing and Hypotheses
    Authors: Banerjee, Anindya ; Naumann, David A. ; Nikouei, Mohammad

    Abstract | Document (562 KB) | BibTeX

    FO-Definable Transformations of Infinite Strings
    Authors: Dave, Vrunda ; Krishna, Shankara Narayanan ; Trivedi, Ashutosh

    Abstract | Document (602 KB) | BibTeX

    Aperiodicity of Rational Functions Is PSPACE-Complete
    Authors: Filiot, Emmanuel ; Gauwin, Olivier ; Lhote, Nathan

    Abstract | Document (528 KB) | BibTeX

    Homomorphism Problems for First-Order Definable Structures
    Authors: Klin, Bartek ; Lasota, Slawomir ; Ochremiak, Joanna ; Torunczyk, Szymon

    Abstract | Document (453 KB) | BibTeX

    On the Sensitivity Conjecture for Disjunctive Normal Forms
    Authors: S., Karthik C. ; Tavenas, Sébastien

    Abstract | Document (547 KB) | BibTeX

    The Zero-Error Randomized Query Complexity of the Pointer Function
    Authors: Radhakrishnan, Jaikumar ; Sanyal, Swagato

    Abstract | Document (608 KB) | BibTeX

    Robust Multiplication-Based Tests for Reed-Muller Codes
    Authors: Harsha, Prahladh ; Srinivasan, Srikanth

    Abstract | Document (546 KB) | BibTeX

    Querying Regular Languages over Sliding Windows
    Authors: Ganardi, Moses ; Hucke, Danny ; Lohrey, Markus

    Abstract | Document (488 KB) | BibTeX

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

    Abstract | Document (583 KB) | BibTeX

    One-Counter Automata with Counter Observability
    Authors: Bollig, Benedikt

    Abstract | Document (562 KB) | BibTeX

    Strong Parameterized Deletion: Bipartite Graphs
    Authors: Rai, Ashutosh ; Ramanujan, M. S.

    Abstract | Document (586 KB) | BibTeX

    Parameterized Algorithms for List K-Cycle
    Authors: Panolan, Fahad ; Zehavi, Meirav

    Abstract | Document (975 KB) | BibTeX

    Lossy Kernels for Graph Contraction Problems
    Authors: Krithika, R. ; Misra, Pranabendu ; Rai, Ashutosh ; Tale, Prafullkumar

    Abstract | Document (520 KB) | BibTeX

    Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments
    Authors: Kumar, Mithilesh ; Lokshtanov, Daniel

    Abstract | Document (543 KB) | BibTeX

    Probabilistic Mu-Calculus: Decidability and Complete Axiomatization
    Authors: Larsen, Kim G. ; Mardare, Radu ; Xue, Bingtian

    Abstract | Document (626 KB) | BibTeX

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

    Abstract | Document (566 KB) | BibTeX

    Model Checking Population Protocols
    Authors: Esparza, Javier ; Ganty, Pierre ; Leroux, Jérôme ; Majumdar, Rupak

    Abstract | Document (534 KB) | BibTeX

    Visibly Linear Dynamic Logic
    Authors: Weinert, Alexander ; Zimmermann, Martin

    Abstract | Document (558 KB) | BibTeX

    Stable Matching Games: Manipulation via Subgraph Isomorphism
    Authors: Gupta, Sushmita ; Roy, Sanjukta

    Abstract | Document (503 KB) | BibTeX

    The Adwords Problem with Strict Capacity Constraints
    Authors: Bhaskar, Umang ; Jalal, Ajil ; Vaze, Rahul

    Abstract | Document (612 KB) | BibTeX

    Most Likely Voronoi Diagrams in Higher Dimensions
    Authors: Kumar, Nirman ; Raichel, Benjamin ; Suri, Subhash ; Verbeek, Kevin

    Abstract | Document (611 KB) | BibTeX

    Fréchet Distance Between a Line and Avatar Point Set
    Authors: Banik, Aritra ; Panolan, Fahad ; Raman, Venkatesh ; Sahlot, Vibha

    Abstract | Document (587 KB) | BibTeX

    Greed is Good for Deterministic Scale-Free Networks
    Authors: Chauhan, Ankit ; Friedrich, Tobias ; Rothenberger, Ralf

    Abstract | Document (605 KB) | BibTeX

    Independent-Set Reconfiguration Thresholds of Hereditary Graph Classes
    Authors: de Berg, Mark ; Jansen, Bart M. P. ; Mukherjee, Debankur

    Abstract | Document (589 KB) | BibTeX

    LZ77 Factorisation of Trees
    Authors: Gawrychowski, Pawel ; Jez, Artur

    Abstract | Document (530 KB) | BibTeX

    Finger Search in Grammar-Compressed Strings
    Authors: Bille, Philip ; Christiansen, Anders Roy ; Cording, Patrick Hagge ; Gortz, Inge Li

    Abstract | Document (588 KB) | BibTeX

    Characterization and Lower Bounds for Branching Program Size Using Projective Dimension
    Authors: Dinesh, Krishnamoorthy ; Koroth, Sajin ; Sarma, Jayalal

    Abstract | Document (552 KB) | BibTeX

    Finer Separations Between Shallow Arithmetic Circuits
    Authors: Kumar, Mrinal ; Saptharishi, Ramprasad

    Abstract | Document (529 KB) | BibTeX

    Sum of Products of Read-Once Formulas
    Authors: C., Ramya ; Rao, B. V. Raghavendra

    Abstract | Document (635 KB) | BibTeX

    Understanding Cutting Planes for QBFs
    Authors: Beyersdorff, Olaf ; Chew, Leroy ; Mahajan, Meena ; Shukla, Anil

    Abstract | Document (531 KB) | BibTeX

    Summaries for Context-Free Games
    Authors: Holík, Lukás ; Meyer, Roland ; Muskalla, Sebastian

    Abstract | Document (558 KB) | BibTeX

    Admissibility in Quantitative Graph Games
    Authors: Brenguier, Romain ; Pérez, Guillermo A. ; Raskin, Jean-Francois ; Sankur, Ocan

    Abstract | Document (522 KB) | BibTeX

    Prompt Delay
    Authors: Klein, Felix ; Zimmermann, Martin

    Abstract | Document (518 KB) | BibTeX

    Mean-Payoff Games on Timed Automata
    Authors: Guha, Shibashis ; Jurdzinski, Marcin ; Krishna, Shankara Narayanan ; Trivedi, Ashutosh

    Abstract | Document (648 KB) | BibTeX

    The Power and Limitations of Uniform Samples in Testing Properties of Figures
    Authors: Berman, Piotr ; Murzabulatov, Meiram ; Raskhodnikova, Sofya

    Abstract | Document (1,874 KB) | BibTeX

    Local Testing for Membership in Lattices
    Authors: Chandrasekaran, Karthekeyan ; Cheraghchi, Mahdi ; Gandikota, Venkata ; Grigorescu, Elena

    Abstract | Document (473 KB) | BibTeX

    Super-Fast MST Algorithms in the Congested Clique Using o(m) Messages
    Authors: Pemmaraju, Sriram V. ; Sardeshmukh, Vivek B.

    Abstract | Document (650 KB) | BibTeX

    Why Liveness for Timed Automata Is Hard, and What We Can Do About It
    Authors: Herbreteau, Frédéric ; Srivathsan, B. ; Tran, Thanh-Tung ; Walukiewicz, Igor

    Abstract | Document (620 KB) | BibTeX

    Verified Analysis of List Update Algorithms
    Authors: Haslbeck, Maximilian P. L. ; Nipkow, Tobias

    Abstract | Document (569 KB) | BibTeX

    Tunable Online MUS/MSS Enumeration
    Authors: Bendík, Jaroslav ; Benes, Nikola ; Cerná, Ivana ; Barnat, Jirí

    Abstract | Document (494 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI