FSTTCS 2017 December 11-15, 2017 - Kanpur, India

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



Satya Lokam and R. Ramanujam (Eds.)
ISBN 978-3-95977-055-2, LIPICS Vol. 93 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 22 MB)
Search Publication Server

Authors
  • Aceto, Luca
  • Achilleos, Antonis
  • Agarwal, Pankaj K.
  • Agrawal, Akanksha
  • Anshu, Anurag
  • Atig, Mohamed Faouzi
  • Bednarczyk, Bartosz
  • Bérard, Béatrice
  • Beyersdorff, Olaf
  • Bhangale, Amey
  • Blondin, Michael
  • Boker, Udi
  • Boninger, Joseph
  • Bouajjani, Ahmed
  • Brandl, Florian
  • Brody, Joshua
  • Cagirici, Onur
  • Cao, Yixin
  • Charatonik, Witold
  • Chattopadhyay, Arkadev
  • Day, Joel D.
  • Demri, Stéphane
  • Ehlers, Rüdiger
  • Elkind, Edith
  • Ene, Alina
  • Finkbeiner, Bernd
  • Finkel, Alain
  • Fleischmann, Pamela
  • Fox, Kyle
  • Francalanza, Adrian
  • Garg, Apoorv
  • Gavinsky, Dmitry
  • Gimbert, Hugo
  • Gölz, Paul
  • Goubault-Larrecq, Jean
  • Grigorescu, Elena
  • Guruganesh, Guru
  • Guruswami, Venkatesan
  • Haddad, Serge
  • Hinde, Luke
  • Hlinený, Petr
  • Huang, Yi
  • Ingólfsdóttir, Anna
  • Jain, Prateek
  • Jain, Rahul
  • Janardhanan, Mano Vikash
  • Kakade, Sham M.
  • Kavitha, Telikepalli
  • Kephart, Owen
  • Ke, Yuping
  • Khot, Subhash
  • Kidambi, Rahul
  • Kini, Dileep
  • Krebs, Andreas
  • Krithika, R.
  • Kumar, Akash
  • Kundu, Srijita
  • Kupferman, Orna
  • Lagerkvist, Victor
  • Lee, Euiwoong
  • Lee, Troy
  • Lefaucheux, Engel
  • Limaye, Nutan
  • Lokam, Satya
  • Lokshtanov, Daniel
  • Louis, Anand
  • Lozes, Etienne
  • Ludwig, Michael
  • Lugiez, Denis
  • Mande, Nikhil S.
  • Manea, Florin
  • Meel, Kuldeep S.
  • Michaliszyn, Jakub
  • Mouawad, Amer E.
  • Mukhopadhyay, Priyanka
  • Muscholl, Anca
  • Nagarajan, Viswanath
  • Narayan Kumar, K.
  • Nasre, Meghana
  • Nath, Abhinandan
  • Netrapalli, Praneeth
  • Nimbhorkar, Prajakta
  • Nowotka, Dirk
  • Otachi, Yota
  • Otop, Jan
  • Parys, Pawel
  • Pich, Ján
  • Pillutla, Venkata Krishna
  • Ramanujam, R.
  • Ramanujan, M. S.
  • Ranade, Abhiram G.
  • Rangarajan, Bharatram
  • Reyzin, Lev
  • Roy, Biman
  • Roy, Bodhayan
  • Sadeqi Azer, Erfan
  • Saivasan, Prakash
  • Saket, Rishi
  • Santha, Miklos
  • Sanyal, Swagato
  • Saurabh, Saket
  • Shah, Devavrat
  • Sharma, Roohani
  • Shrotri, Aditya A.
  • Sidford, Aaron
  • Skrzypczak, Michal
  • Thiruvenkatachari, Devanathan
  • Tulsiani, Madhur
  • Vaikuntanathan, Vinod
  • Vardi, Gal
  • Vardi, Moshe Y.
  • Viswanathan, Mahesh
  • Weinert, Alexander
  • Wieczorek, Piotr
  • Wilke, Thomas
  • You, Jie
  • Zehavi, Meirav
  • Zhou, Samson
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Lokam, Satya ; Ramanujam, R.

    Abstract | Document (318 KB) | BibTeX

    Justified Representation in Multiwinner Voting: Axioms and Algorithms
    Authors: Elkind, Edith

    Abstract | Document (345 KB) | BibTeX

    A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)
    Authors: Jain, Prateek ; Kakade, Sham M. ; Kidambi, Rahul ; Netrapalli, Praneeth ; Pillutla, Venkata Krishna ; Sidford, Aaron

    Abstract | Document (384 KB) | BibTeX

    Automated Synthesis: a Distributed Viewpoint
    Authors: Muscholl, Anca

    Abstract | Document (264 KB) | BibTeX

    Matrix Estimation, Latent Variable Model and Collaborative Filtering
    Authors: Shah, Devavrat

    Abstract | Document (420 KB) | BibTeX

    Some Open Problems in Information-Theoretic Cryptography
    Authors: Vaikuntanathan, Vinod

    Abstract | Document (309 KB) | BibTeX

    Backward Deterministic Büchi Automata on Infinite Words
    Authors: Wilke, Thomas

    Abstract | Document (392 KB) | BibTeX

    Monitoring for Silent Actions
    Authors: Aceto, Luca ; Achilleos, Antonis ; Francalanza, Adrian ; Ingólfsdóttir, Anna

    Abstract | Document (531 KB) | BibTeX

    Maintaining Reeb Graphs of Triangulated 2-Manifolds
    Authors: Agarwal, Pankaj K. ; Fox, Kyle ; Nath, Abhinandan

    Abstract | Document (620 KB) | BibTeX

    On the Parameterized Complexity of Simultaneous Deletion Problems
    Authors: Agrawal, Akanksha ; Krithika, R. ; Lokshtanov, Daniel ; Mouawad, Amer E. ; Ramanujan, M. S.

    Abstract | Document (633 KB) | BibTeX

    A Composition Theorem for Randomized Query Complexity
    Authors: Anshu, Anurag ; Gavinsky, Dmitry ; Jain, Rahul ; Kundu, Srijita ; Lee, Troy ; Mukhopadhyay, Priyanka ; Santha, Miklos ; Sanyal, Swagato

    Abstract | Document (542 KB) | BibTeX

    Verification of Asynchronous Programs with Nested Locks
    Authors: Atig, Mohamed Faouzi ; Bouajjani, Ahmed ; Narayan Kumar, K. ; Saivasan, Prakash

    Abstract | Document (513 KB) | BibTeX

    Modulo Counting on Words and Trees
    Authors: Bednarczyk, Bartosz ; Charatonik, Witold

    Abstract | Document (639 KB) | BibTeX

    Probabilistic Disclosure: Maximisation vs. Minimisation
    Authors: Bérard, Béatrice ; Haddad, Serge ; Lefaucheux, Engel

    Abstract | Document (578 KB) | BibTeX

    Reasons for Hardness in QBF Proof Systems
    Authors: Beyersdorff, Olaf ; Hinde, Luke ; Pich, Ján

    Abstract | Document (497 KB) | BibTeX

    An Improved Dictatorship Test with Perfect Completeness
    Authors: Bhangale, Amey ; Khot, Subhash ; Thiruvenkatachari, Devanathan

    Abstract | Document (654 KB) | BibTeX

    Forward Analysis for WSTS, Part III: Karp-Miller Trees
    Authors: Blondin, Michael ; Finkel, Alain ; Goubault-Larrecq, Jean

    Abstract | Document (600 KB) | BibTeX

    Rabin vs. Streett Automata
    Authors: Boker, Udi

    Abstract | Document (504 KB) | BibTeX

    How Deterministic are Good-For-Games Automata?
    Authors: Boker, Udi ; Kupferman, Orna ; Skrzypczak, Michal

    Abstract | Document (525 KB) | BibTeX

    Popular Matchings with Multiple Partners
    Authors: Brandl, Florian ; Kavitha, Telikepalli

    Abstract | Document (555 KB) | BibTeX

    Non-Adaptive Data Structure Bounds for Dynamic Predecessor
    Authors: Boninger, Joseph ; Brody, Joshua ; Kephart, Owen

    Abstract | Document (489 KB) | BibTeX

    On Colourability of Polygon Visibility Graphs
    Authors: Cagirici, Onur ; Hlinený, Petr ; Roy, Bodhayan

    Abstract | Document (611 KB) | BibTeX

    Vertex Deletion Problems on Chordal Graphs
    Authors: Cao, Yixin ; Ke, Yuping ; Otachi, Yota ; You, Jie

    Abstract | Document (584 KB) | BibTeX

    A Lifting Theorem with Applications to Symmetric Functions
    Authors: Chattopadhyay, Arkadev ; Mande, Nikhil S.

    Abstract | Document (552 KB) | BibTeX

    Local Patterns
    Authors: Day, Joel D. ; Fleischmann, Pamela ; Manea, Florin ; Nowotka, Dirk

    Abstract | Document (567 KB) | BibTeX

    On Symbolic Heaps Modulo Permission Theories
    Authors: Demri, Stéphane ; Lozes, Etienne ; Lugiez, Denis

    Abstract | Document (663 KB) | BibTeX

    Symmetric Synthesis
    Authors: Ehlers, Rüdiger ; Finkbeiner, Bernd

    Abstract | Document (536 KB) | BibTeX

    Approximation Algorithms for Stochastic k-TSP
    Authors: Ene, Alina ; Nagarajan, Viswanath ; Saket, Rishi

    Abstract | Document (537 KB) | BibTeX

    Synthesis in Distributed Environments
    Authors: Finkbeiner, Bernd ; Gölz, Paul

    Abstract | Document (512 KB) | BibTeX

    Train Scheduling on a Unidirectional Path
    Authors: Garg, Apoorv ; Ranade, Abhiram G.

    Abstract | Document (600 KB) | BibTeX

    On the Control of Asynchronous Automata
    Authors: Gimbert, Hugo

    Abstract | Document (573 KB) | BibTeX

    Streaming for Aibohphobes: Longest Palindrome with Mismatches
    Authors: Grigorescu, Elena ; Sadeqi Azer, Erfan ; Zhou, Samson

    Abstract | Document (582 KB) | BibTeX

    Understanding the Correlation Gap For Matchings
    Authors: Guruganesh, Guru ; Lee, Euiwoong

    Abstract | Document (522 KB) | BibTeX

    Hardness of Rainbow Coloring Hypergraphs
    Authors: Guruswami, Venkatesan ; Saket, Rishi

    Abstract | Document (575 KB) | BibTeX

    Network Construction with Ordered Constraints
    Authors: Huang, Yi ; Janardhanan, Mano Vikash ; Reyzin, Lev

    Abstract | Document (539 KB) | BibTeX

    Complexity of Model Checking MDPs against LTL Specifications
    Authors: Kini, Dileep ; Viswanathan, Mahesh

    Abstract | Document (534 KB) | BibTeX

    A Unified Method for Placing Problems in Polylogarithmic Depth
    Authors: Krebs, Andreas ; Limaye, Nutan ; Ludwig, Michael

    Abstract | Document (562 KB) | BibTeX

    Finding Pseudorandom Colorings of Pseudorandom Graphs
    Authors: Kumar, Akash ; Louis, Anand ; Tulsiani, Madhur

    Abstract | Document (481 KB) | BibTeX

    Flow Games
    Authors: Kupferman, Orna ; Vardi, Gal ; Vardi, Moshe Y.

    Abstract | Document (572 KB) | BibTeX

    A Dichotomy Theorem for the Inverse Satisfiability Problem
    Authors: Lagerkvist, Victor ; Roy, Biman

    Abstract | Document (573 KB) | BibTeX

    Balanced Judicious Bipartition is Fixed-Parameter Tractable
    Authors: Lokshtanov, Daniel ; Saurabh, Saket ; Sharma, Roohani ; Zehavi, Meirav

    Abstract | Document (748 KB) | BibTeX

    On Hashing-Based Approaches to Approximate DNF-Counting
    Authors: Meel, Kuldeep S. ; Shrotri, Aditya A. ; Vardi, Moshe Y.

    Abstract | Document (609 KB) | BibTeX

    Average Stack Cost of Büchi Pushdown Automata
    Authors: Michaliszyn, Jakub ; Otop, Jan

    Abstract | Document (536 KB) | BibTeX

    Querying Best Paths in Graph Databases
    Authors: Michaliszyn, Jakub ; Otop, Jan ; Wieczorek, Piotr

    Abstract | Document (601 KB) | BibTeX

    Popular Matchings with Lower Quotas
    Authors: Nasre, Meghana ; Nimbhorkar, Prajakta

    Abstract | Document (586 KB) | BibTeX

    The Complexity of the Diagonal Problem for Recursion Schemes
    Authors: Parys, Pawel

    Abstract | Document (540 KB) | BibTeX

    A Combinatorial Proof of Ihara-Bass's Formula for the Zeta Function of Regular Graphs
    Authors: Rangarajan, Bharatram

    Abstract | Document (431 KB) | BibTeX

    VLDL Satisfiability and Model Checking via Tree Automata
    Authors: Weinert, Alexander

    Abstract | Document (564 KB) | BibTeX

    		  



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