FSTTCS 2018 December 11-13, 2018 - Ahmedabad, India

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



Sumit Ganguly and Paritosh Pandya (Eds.)
ISBN 978-3-95977-093-4, LIPICS Vol. 122 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 22 MB)
Search Publication Server

Authors
  • Abdulla, Parosh Aziz
  • Abu Zaid, Faried
  • Alambardar Meybodi, Mohsen
  • Arvind, V.
  • Asada, Kazuyuki
  • Atig, Mohamed Faouzi
  • Babay, Amy
  • Baelde, David
  • Bagnol, Marc
  • Bansal, Manisha
  • Bauer, Balthazar
  • Bhandari, Siddharth
  • Bhaskar, Umang
  • Bläser, Markus
  • Boiret, Adrien
  • Boker, Udi
  • Bose, Sougata
  • Bringmann, Karl
  • Busatto-Gaston, Damien
  • Bérard, Béatrice
  • C. S., Karthik
  • Chatterjee, Abhranil
  • Chaubal, Siddhesh
  • Chaudhury, Bhaskar Ray
  • Cheung, Yun Kuen
  • Cseh, Ágnes
  • Datta, Rajit
  • Datta, Samir
  • Debant, Alexandre
  • Delaune, Stéphanie
  • Dinitz, Michael
  • Filiot, Emmanuel
  • Finkel, Alain
  • Fomin, Fedor
  • Ganguly, Sumit
  • Ganty, Pierre
  • Garg, Jugal
  • Garg, Naveen
  • Gauwin, Olivier
  • Geeraerts, Gilles
  • Ghosh, Abheek
  • Goldenberg, Elazar
  • Grover, Sapna
  • Guha, Shibashis
  • Gupta, Neelima
  • Gutiérrez, Elena
  • Gál, Anna
  • Haar, Stefan
  • Harsha, Prahladh
  • Hoefer, Martin
  • Honsell, Furio
  • Hélouët, Loic
  • Iyer, Siddharth
  • Kavitha, Telikepalli
  • Kesh, Deepanjan
  • Khuller, Samir
  • Kobayashi, Naoki
  • Komarath, Balagopal
  • Krishna, Shankara Narayanan
  • Kulkarni, Raghav
  • Kuperberg, Denis
  • Köcher, Chris
  • Le Roux, Stéphane
  • Lehtinen, Karoliina
  • Leroux, Jérôme
  • Lhote, Nathan
  • Lick, Anthony
  • Liquori, Luigi
  • Luo, Junjie
  • Majumdar, Rupak
  • Mansutti, Alessio
  • Mehlhorn, Kurt
  • Misra, Pranabendu
  • Molli, Tulasimohan
  • Molter, Hendrik
  • Monmege, Benjamin
  • Mouawad, Amer E.
  • Mukherjee, Anish
  • Mukhopadhyay, Partha
  • Muscholl, Anca
  • N. Prabhakar, Swaroop
  • Nichterlein, André
  • Niedermeier, Rolf
  • Padmanabha, Anantha
  • Pancholi, Aditya
  • Pandya, Paritosh
  • Panolan, Fahad
  • Pauly, Arno
  • Penelle, Vincent
  • Piórkowski, Radoslaw
  • Place, Thomas
  • Puppis, Gabriele
  • Ramanujam, R
  • Randour, Mickael
  • Raskin, Jean-François
  • Reynier, Pierre-Alain
  • Salvati, Sylvain
  • Saptharishi, Ramprasad
  • Saurabh, Saket
  • Scagnetto, Ivan
  • Schmitz, Sylvain
  • Schmude, Janusz
  • Sharma, Roohani
  • Sharma, Vikram
  • Sistla, A. Prasad
  • Sreenivasaiah, Karteek
  • Srinivasan, Srikanth
  • Stolze, Claude
  • Sutre, Grégoire
  • Svensson, Ola
  • Tengse, Anamay
  • Tirodkar, Sumedh
  • Vaidya, Shaan
  • Vempala, Santosh
  • Vihrovs, Jevgenijs
  • Wang, Yanjing
  • Wee, Hoeteck
  • Wiedling, Cyrille
  • Zehavi, Meirav
  • Zeitoun, Marc
  • Zhang, Zeyu
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Ganguly, Sumit ; Pandya, Paritosh

    Abstract | Document (307 KB) | BibTeX

    Random Testing for Distributed Systems with Theoretical Guarantees (Invited Paper)
    Authors: Majumdar, Rupak

    Abstract | Document (181 KB) | BibTeX

    Model Checking Randomized Security Protocols (Invited Paper)
    Authors: Sistla, A. Prasad

    Abstract | Document (158 KB) | BibTeX

    Algorithms for the Asymmetric Traveling Salesman Problem (Invited Paper)
    Authors: Svensson, Ola

    Abstract | Document (226 KB) | BibTeX

    Continuous Algorithms (Invited Paper)
    Authors: Vempala, Santosh

    Abstract | Document (156 KB) | BibTeX

    On the Probabilistic Degree of OR over the Reals
    Authors: Bhandari, Siddharth ; Harsha, Prahladh ; Molli, Tulasimohan ; Srinivasan, Srikanth

    Abstract | Document (475 KB) | BibTeX

    Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees
    Authors: Saptharishi, Ramprasad ; Tengse, Anamay

    Abstract | Document (536 KB) | BibTeX

    Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators
    Authors: Arvind, V. ; Chatterjee, Abhranil ; Datta, Rajit ; Mukhopadhyay, Partha

    Abstract | Document (542 KB) | BibTeX

    Verification of Timed Asynchronous Programs
    Authors: Abdulla, Parosh Aziz ; Atig, Mohamed Faouzi ; Krishna, Shankara Narayanan ; Vaidya, Shaan

    Abstract | Document (539 KB) | BibTeX

    The Cayley-Graph of the Queue Monoid: Logic and Decidability
    Authors: Abu Zaid, Faried ; Köcher, Chris

    Abstract | Document (521 KB) | BibTeX

    Uniformly Automatic Classes of Finite Structures
    Authors: Abu Zaid, Faried

    Abstract | Document (623 KB) | BibTeX

    Towards a General Direct Product Testing Theorem
    Authors: Goldenberg, Elazar ; C. S., Karthik

    Abstract | Document (581 KB) | BibTeX

    Space Complexity of Two Adaptive Bitprobe Schemes Storing Three Elements
    Authors: Kesh, Deepanjan

    Abstract | Document (393 KB) | BibTeX

    New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity
    Authors: Chaubal, Siddhesh ; Gál, Anna

    Abstract | Document (440 KB) | BibTeX

    Lambda-Definable Order-3 Tree Functions are Well-Quasi-Ordered
    Authors: Asada, Kazuyuki ; Kobayashi, Naoki

    Abstract | Document (551 KB) | BibTeX

    A Hypersequent Calculus with Clusters for Tense Logic over Ordinals
    Authors: Baelde, David ; Lick, Anthony ; Schmitz, Sylvain

    Abstract | Document (593 KB) | BibTeX

    Büchi Good-for-Games Automata Are Efficiently Recognizable
    Authors: Bagnol, Marc ; Kuperberg, Denis

    Abstract | Document (514 KB) | BibTeX

    Popular Matchings in Complete Graphs
    Authors: Cseh, Ágnes ; Kavitha, Telikepalli

    Abstract | Document (450 KB) | BibTeX

    Graph Pattern Polynomials
    Authors: Bläser, Markus ; Komarath, Balagopal ; Sreenivasaiah, Karteek

    Abstract | Document (464 KB) | BibTeX

    Shortest k-Disjoint Paths via Determinants
    Authors: Datta, Samir ; Iyer, Siddharth ; Kulkarni, Raghav ; Mukherjee, Anish

    Abstract | Document (873 KB) | BibTeX

    Hyper Partial Order Logic
    Authors: Bérard, Béatrice ; Haar, Stefan ; Hélouët, Loic

    Abstract | Document (527 KB) | BibTeX

    On the Way to Alternating Weak Automata
    Authors: Boker, Udi ; Lehtinen, Karoliina

    Abstract | Document (534 KB) | BibTeX

    Origin-Equivalence of Two-Way Word Transducers Is in PSPACE
    Authors: Bose, Sougata ; Muscholl, Anca ; Penelle, Vincent ; Puppis, Gabriele

    Abstract | Document (548 KB) | BibTeX

    Constant Factor Approximation Algorithm for Uniform Hard Capacitated Knapsack Median Problem
    Authors: Grover, Sapna ; Gupta, Neelima ; Khuller, Samir ; Pancholi, Aditya

    Abstract | Document (800 KB) | BibTeX

    A 5-Approximation for Universal Facility Location
    Authors: Bansal, Manisha ; Garg, Naveen ; Gupta, Neelima

    Abstract | Document (458 KB) | BibTeX

    On Fair Division for Indivisible Items
    Authors: Chaudhury, Bhaskar Ray ; Cheung, Yun Kuen ; Garg, Jugal ; Garg, Naveen ; Hoefer, Martin ; Mehlhorn, Kurt

    Abstract | Document (588 KB) | BibTeX

    Combinatorial Algorithms for General Linear Arrow-Debreu Markets
    Authors: Chaudhury, Bhaskar Ray ; Mehlhorn, Kurt

    Abstract | Document (501 KB) | BibTeX

    On the Welfare of Cardinal Voting Mechanisms
    Authors: Bhaskar, Umang ; Ghosh, Abheek

    Abstract | Document (518 KB) | BibTeX

    Symbolic Approximation of Weighted Timed Games
    Authors: Busatto-Gaston, Damien ; Monmege, Benjamin ; Reynier, Pierre-Alain

    Abstract | Document (533 KB) | BibTeX

    A Symbolic Framework to Analyse Physical Proximity in Security Protocols
    Authors: Debant, Alexandre ; Delaune, Stéphanie ; Wiedling, Cyrille

    Abstract | Document (560 KB) | BibTeX

    On Canonical Models for Rational Functions over Infinite Words
    Authors: Filiot, Emmanuel ; Gauwin, Olivier ; Lhote, Nathan ; Muscholl, Anca

    Abstract | Document (507 KB) | BibTeX

    Reachability for Two-Counter Machines with One Test and One Reset
    Authors: Finkel, Alain ; Leroux, Jérôme ; Sutre, Grégoire

    Abstract | Document (535 KB) | BibTeX

    The Parikh Property for Weighted Context-Free Grammars
    Authors: Ganty, Pierre ; Gutiérrez, Elena

    Abstract | Document (583 KB) | BibTeX

    Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network
    Authors: Babay, Amy ; Dinitz, Michael ; Zhang, Zeyu

    Abstract | Document (771 KB) | BibTeX

    On the Parameterized Complexity of [1,j]-Domination Problems
    Authors: Alambardar Meybodi, Mohsen ; Fomin, Fedor ; Mouawad, Amer E. ; Panolan, Fahad

    Abstract | Document (713 KB) | BibTeX

    Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number
    Authors: Misra, Pranabendu ; Saurabh, Saket ; Sharma, Roohani ; Zehavi, Meirav

    Abstract | Document (721 KB) | BibTeX

    Safe and Optimal Scheduling for Hard and Soft Tasks
    Authors: Geeraerts, Gilles ; Guha, Shibashis ; Raskin, Jean-François

    Abstract | Document (607 KB) | BibTeX

    The Delta-Framework
    Authors: Honsell, Furio ; Liquori, Luigi ; Stolze, Claude ; Scagnetto, Ivan

    Abstract | Document (600 KB) | BibTeX

    Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
    Authors: Le Roux, Stéphane ; Pauly, Arno ; Randour, Mickael

    Abstract | Document (482 KB) | BibTeX

    Deterministic Algorithms for Maximum Matching on General Graphs in the Semi-Streaming Model
    Authors: Tirodkar, Sumedh

    Abstract | Document (487 KB) | BibTeX

    Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS
    Authors: Bringmann, Karl ; Chaudhury, Bhaskar Ray

    Abstract | Document (515 KB) | BibTeX

    On the Inner Product Predicate and a Generalization of Matching Vector Families
    Authors: Bauer, Balthazar ; Vihrovs, Jevgenijs ; Wee, Hoeteck

    Abstract | Document (484 KB) | BibTeX

    Extending Propositional Separation Logic for Robustness Properties
    Authors: Mansutti, Alessio

    Abstract | Document (709 KB) | BibTeX

    Bundled Fragments of First-Order Modal Logic: (Un)Decidability
    Authors: Padmanabha, Anantha ; Ramanujam, R ; Wang, Yanjing

    Abstract | Document (619 KB) | BibTeX

    On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems
    Authors: Penelle, Vincent ; Salvati, Sylvain ; Sutre, Grégoire

    Abstract | Document (662 KB) | BibTeX

    Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model
    Authors: N. Prabhakar, Swaroop ; Sharma, Vikram

    Abstract | Document (486 KB) | BibTeX

    Parameterized Dynamic Cluster Editing
    Authors: Luo, Junjie ; Molter, Hendrik ; Nichterlein, André ; Niedermeier, Rolf

    Abstract | Document (509 KB) | BibTeX

    The Complexity of Separation for Levels in Concatenation Hierarchies
    Authors: Place, Thomas ; Zeitoun, Marc

    Abstract | Document (526 KB) | BibTeX

    Reducing Transducer Equivalence to Register Automata Problems Solved by "Hilbert Method"
    Authors: Boiret, Adrien ; Piórkowski, Radoslaw ; Schmude, Janusz

    Abstract | Document (509 KB) | BibTeX

    		  



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