FSTTCS 2019 December 11-13, 2019, Bombay, India

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



Arkadev Chattopadhyay and Paul Gastin (Eds.)
ISBN 978-3-95977-131-3, LIPICS Vol. 150 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 24 MB)
Search Publication Server

Authors
  • Adler, Isolde
  • Agrawal, Akanksha
  • Ahn, Hee-Kap
  • Akshay, S.
  • Arvind, V.
  • Baldan, Paolo
  • Bazille, Hugo
  • Bertrand, Nathalie
  • Bhargavan, Karthikeyan
  • Biswas, Arindam
  • Bonnet, Édouard
  • Bordais, Benjamin
  • Bouyer, Patricia
  • Bozzelli, Laura
  • Brettell, Nick
  • Brihaye, Thomas
  • Chakraborty, Diptarka
  • Chatterjee, Abhranil
  • Chatterjee, Prerona
  • Chattopadhyay, Agnishom
  • Chattopadhyay, Arkadev
  • Chini, Peter
  • Choi, Yujin
  • Curticapean, Radu
  • Das, Debarati
  • Datta, Rajit
  • Dreier, Jan
  • Droste, Manfred
  • Dudek, Jeffrey M.
  • Dziadek, Sven
  • Fabre, Eric
  • Filiot, Emmanuel
  • Finkel, Alain
  • Fomin, Fedor V.
  • Fournier, Hervé
  • Fried, Dror
  • Gadducci, Fabio
  • Gastin, Paul
  • Geeraerts, Gilles
  • Genest, Blaise
  • Golovach, Petr A.
  • Guha, Shibashis
  • Gupta, Chetan
  • Gupta, Ekanshdeep
  • Hallet, Marion
  • Hoi, Gordon
  • Jain, Pallavi
  • Jain, Rahul
  • Jain, Sanjay
  • Kanesh, Lawqueen
  • Kavitha, Telikepalli
  • Kleine Büning, Hans
  • Kolisetty, Sanjana
  • Koucký, Michal
  • Krauthgamer, Robert
  • Kuhlmann, Marco
  • Kuich, Werner
  • Kuperberg, Denis
  • La Torre, Salvatore
  • Lazic, Ranko
  • Lee, Seungjun
  • Le, Linh
  • Leroux, Jérôme
  • Limaye, Nutan
  • Lochet, William
  • Louis, Anand
  • Lucarelli, Giorgio
  • Majumdar, Anirban
  • Maletti, Andreas
  • Malod, Guillaume
  • Mansard, Alexandre
  • Marx, Dániel
  • Mazzocchi, Nicolas
  • Melgratti, Hernán
  • Mestel, David
  • Meyer, Roland
  • Miltzow, Tillmann
  • Monmege, Benjamin
  • Montanari, Angelo
  • Moseley, Benjamin
  • Mukhopadhyay, Partha
  • Naldurg, Prasad
  • Parthasarathy, Madhusudan
  • Paul, Christophe
  • Peron, Adriano
  • Pinault, Laureline
  • Pitassi, Toniann
  • Potukuchi, Aditya
  • Pous, Damien
  • Praveen, M.
  • Quoitin, Bruno
  • Rabinovich, Alexander
  • Raffaetà, Alessandra
  • Raman, Venkatesh
  • Raskin, Jean-François
  • Roldán, Christian
  • Rossmanith, Peter
  • Roughgarden, Tim
  • Saivasan, Prakash
  • Sammartino, Matteo
  • Saptharishi, Ramprasad
  • Sarpatwar, Kanthi
  • Saurabh, Saket
  • Schieber, Baruch
  • Schiffer, Lena Katharina
  • Schwartz, Roy
  • Shachnai, Hadas
  • Sharma, Roohani
  • Sharma, Vimal Raj
  • Silva, Alexandra
  • Simonov, Kirill
  • Singh, Mohit
  • Srinivasan, Srikanth
  • Srivastav, Abhinav
  • Stephan, Frank
  • Subramani, K.
  • Szusterman, Maud
  • Tavenas, Sébastien
  • Tewari, Raghunath
  • Thang, Nguyen Kim
  • Thilikos, Dimitrios M.
  • Thinniyam, Ramanathan S.
  • Tiferet, Doron
  • Tripathi, Utkarsh
  • Trystram, Denis
  • Venkat, Rakesh
  • Venkitesh, S.
  • Volkovich, Ilya
  • Wojciechowski, Piotr
  • Yannakakis, Mihalis
  • Yazdanbod, Sina
  • Zetzsche, Georg
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Chattopadhyay, Arkadev ; Gastin, Paul

    Abstract | Document (297 KB) | BibTeX

    Practical Formal Methods for Real World Cryptography (Invited Talk)
    Authors: Bhargavan, Karthikeyan ; Naldurg, Prasad

    Abstract | Document (922 KB) | BibTeX

    Sketching Graphs and Combinatorial Optimization (Invited Talk)
    Authors: Krauthgamer, Robert

    Abstract | Document (178 KB) | BibTeX

    Finkel Was Right: Counter-Examples to Several Conjectures on Variants of Vector Addition Systems (Invited Talk)
    Authors: Lazic, Ranko

    Abstract | Document (281 KB) | BibTeX

    Progress in Lifting and Applications in Lower Bounds (Invited Talk)
    Authors: Pitassi, Toniann

    Abstract | Document (157 KB) | BibTeX

    How Computer Science Informs Modern Auction Design (Invited Talk)
    Authors: Roughgarden, Tim

    Abstract | Document (159 KB) | BibTeX

    An Algebraic Framework to Reason About Concurrency (Invited Talk)
    Authors: Silva, Alexandra

    Abstract | Document (204 KB) | BibTeX

    Connected Search for a Lazy Robber
    Authors: Adler, Isolde ; Paul, Christophe ; Thilikos, Dimitrios M.

    Abstract | Document (820 KB) | BibTeX

    Parameterized Streaming Algorithms for Min-Ones d-SAT
    Authors: Agrawal, Akanksha ; Biswas, Arindam ; Bonnet, Édouard ; Brettell, Nick ; Curticapean, Radu ; Marx, Dániel ; Miltzow, Tillmann ; Raman, Venkatesh ; Saurabh, Saket

    Abstract | Document (728 KB) | BibTeX

    Fast Exact Algorithms Using Hadamard Product of Polynomials
    Authors: Arvind, V. ; Chatterjee, Abhranil ; Datta, Rajit ; Mukhopadhyay, Partha

    Abstract | Document (515 KB) | BibTeX

    Approximate Online Pattern Matching in Sublinear Time
    Authors: Chakraborty, Diptarka ; Das, Debarati ; Koucký, Michal

    Abstract | Document (492 KB) | BibTeX

    Constructing Faithful Homomorphisms over Fields of Finite Characteristic
    Authors: Chatterjee, Prerona ; Saptharishi, Ramprasad

    Abstract | Document (531 KB) | BibTeX

    Maximum-Area Rectangles in a Simple Polygon
    Authors: Choi, Yujin ; Lee, Seungjun ; Ahn, Hee-Kap

    Abstract | Document (664 KB) | BibTeX

    Motif Counting in Preferential Attachment Graphs
    Authors: Dreier, Jan ; Rossmanith, Peter

    Abstract | Document (474 KB) | BibTeX

    Parameterized k-Clustering: Tractability Island
    Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Simonov, Kirill

    Abstract | Document (562 KB) | BibTeX

    Nonnegative Rank Measures and Monotone Algebraic Branching Programs
    Authors: Fournier, Hervé ; Malod, Guillaume ; Szusterman, Maud ; Tavenas, Sébastien

    Abstract | Document (494 KB) | BibTeX

    Unambiguous Catalytic Computation
    Authors: Gupta, Chetan ; Jain, Rahul ; Sharma, Vimal Raj ; Tewari, Raghunath

    Abstract | Document (539 KB) | BibTeX

    A Fast Exponential Time Algorithm for Max Hamming Distance X3SAT
    Authors: Hoi, Gordon ; Jain, Sanjay ; Stephan, Frank

    Abstract | Document (518 KB) | BibTeX

    Exact and Approximate Digraph Bandwidth
    Authors: Jain, Pallavi ; Kanesh, Lawqueen ; Lochet, William ; Saurabh, Saket ; Sharma, Roohani

    Abstract | Document (759 KB) | BibTeX

    An O(n^(1/4 +epsilon)) Space and Polynomial Algorithm for Grid Graph Reachability
    Authors: Jain, Rahul ; Tewari, Raghunath

    Abstract | Document (595 KB) | BibTeX

    Popular Roommates in Simply Exponential Time
    Authors: Kavitha, Telikepalli

    Abstract | Document (502 KB) | BibTeX

    The Complexity of Finding S-Factors in Regular Graphs
    Authors: Kolisetty, Sanjana ; Le, Linh ; Volkovich, Ilya ; Yannakakis, Mihalis

    Abstract | Document (488 KB) | BibTeX

    More on AC^0[oplus] and Variants of the Majority Function
    Authors: Limaye, Nutan ; Srinivasan, Srikanth ; Tripathi, Utkarsh

    Abstract | Document (612 KB) | BibTeX

    Planted Models for k-Way Edge and Vertex Expansion
    Authors: Louis, Anand ; Venkat, Rakesh

    Abstract | Document (552 KB) | BibTeX

    Online Non-Preemptive Scheduling to Minimize Maximum Weighted Flow-Time on Related Machines
    Authors: Lucarelli, Giorgio ; Moseley, Benjamin ; Thang, Nguyen Kim ; Srivastav, Abhinav ; Trystram, Denis

    Abstract | Document (427 KB) | BibTeX

    On the AC^0[oplus] Complexity of Andreev's Problem
    Authors: Potukuchi, Aditya

    Abstract | Document (574 KB) | BibTeX

    The Preemptive Resource Allocation Problem
    Authors: Sarpatwar, Kanthi ; Schieber, Baruch ; Shachnai, Hadas

    Abstract | Document (519 KB) | BibTeX

    Online and Offline Algorithms for Circuit Switch Scheduling
    Authors: Schwartz, Roy ; Singh, Mohit ; Yazdanbod, Sina

    Abstract | Document (547 KB) | BibTeX

    On the Probabilistic Degrees of Symmetric Boolean Functions
    Authors: Srinivasan, Srikanth ; Tripathi, Utkarsh ; Venkitesh, S.

    Abstract | Document (557 KB) | BibTeX

    Classification Among Hidden Markov Models
    Authors: Akshay, S. ; Bazille, Hugo ; Fabre, Eric ; Genest, Blaise

    Abstract | Document (519 KB) | BibTeX

    Minimisation of Event Structures
    Authors: Baldan, Paolo ; Raffaetà, Alessandra

    Abstract | Document (533 KB) | BibTeX

    Concurrent Parameterized Games
    Authors: Bertrand, Nathalie ; Bouyer, Patricia ; Majumdar, Anirban

    Abstract | Document (596 KB) | BibTeX

    Expected Window Mean-Payoff
    Authors: Bordais, Benjamin ; Guha, Shibashis ; Raskin, Jean-François

    Abstract | Document (626 KB) | BibTeX

    Interval Temporal Logic for Visibly Pushdown Systems
    Authors: Bozzelli, Laura ; Montanari, Angelo ; Peron, Adriano

    Abstract | Document (596 KB) | BibTeX

    Taming the Complexity of Timeline-Based Planning over Dense Temporal Domains
    Authors: Bozzelli, Laura ; Montanari, Angelo ; Peron, Adriano

    Abstract | Document (575 KB) | BibTeX

    Dynamics on Games: Simulation-Based Techniques and Applications to Routing
    Authors: Brihaye, Thomas ; Geeraerts, Gilles ; Hallet, Marion ; Monmege, Benjamin ; Quoitin, Bruno

    Abstract | Document (503 KB) | BibTeX

    Query Preserving Watermarking Schemes for Locally Treelike Databases
    Authors: Chattopadhyay, Agnishom ; Praveen, M.

    Abstract | Document (524 KB) | BibTeX

    Complexity of Liveness in Parameterized Systems
    Authors: Chini, Peter ; Meyer, Roland ; Saivasan, Prakash

    Abstract | Document (515 KB) | BibTeX

    Greibach Normal Form for omega-Algebraic Systems and Weighted Simple omega-Pushdown Automata
    Authors: Droste, Manfred ; Dziadek, Sven ; Kuich, Werner

    Abstract | Document (463 KB) | BibTeX

    Transformations of Boolean Functions
    Authors: Dudek, Jeffrey M. ; Fried, Dror

    Abstract | Document (491 KB) | BibTeX

    Two-Way Parikh Automata
    Authors: Filiot, Emmanuel ; Guha, Shibashis ; Mazzocchi, Nicolas

    Abstract | Document (586 KB) | BibTeX

    The Well Structured Problem for Presburger Counter Machines
    Authors: Finkel, Alain ; Gupta, Ekanshdeep

    Abstract | Document (560 KB) | BibTeX

    A Categorical Account of Replicated Data Types
    Authors: Gadducci, Fabio ; Melgratti, Hernán ; Roldán, Christian ; Sammartino, Matteo

    Abstract | Document (602 KB) | BibTeX

    New Results on Cutting Plane Proofs for Horn Constraint Systems
    Authors: Kleine Büning, Hans ; Wojciechowski, Piotr ; Subramani, K.

    Abstract | Document (467 KB) | BibTeX

    The Tree-Generative Capacity of Combinatory Categorial Grammars
    Authors: Kuhlmann, Marco ; Maletti, Andreas ; Schiffer, Lena Katharina

    Abstract | Document (576 KB) | BibTeX

    Cyclic Proofs and Jumping Automata
    Authors: Kuperberg, Denis ; Pinault, Laureline ; Pous, Damien

    Abstract | Document (588 KB) | BibTeX

    Reachability in Concurrent Uninterpreted Programs
    Authors: La Torre, Salvatore ; Parthasarathy, Madhusudan

    Abstract | Document (588 KB) | BibTeX

    Distance Between Mutually Reachable Petri Net Configurations
    Authors: Leroux, Jérôme

    Abstract | Document (477 KB) | BibTeX

    Boolean Algebras from Trace Automata
    Authors: Mansard, Alexandre

    Abstract | Document (696 KB) | BibTeX

    Widths of Regular and Context-Free Languages
    Authors: Mestel, David

    Abstract | Document (469 KB) | BibTeX

    Degrees of Ambiguity of Büchi Tree Automata
    Authors: Rabinovich, Alexander ; Tiferet, Doron

    Abstract | Document (520 KB) | BibTeX

    Regular Separability and Intersection Emptiness Are Independent Problems
    Authors: Thinniyam, Ramanathan S. ; Zetzsche, Georg

    Abstract | Document (553 KB) | BibTeX

    		  



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