FSTTCS 2017
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Indian Institute of Technology, Kanpur. December 11–15, 2017.
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Indian Institute of Technology, Kanpur. December 11–15, 2017.
Luca Aceto, Antonis Achilleos, Adrian Francalanza and Anna Ingólfsdóttir
Monitoring for Silent Actions
Pankaj K. Agarwal, Kyle Fox and Abhinandan Nath
Maintaining Reeb graphs of triangulated 2-manifolds
Akanksha Agrawal, R. Krithika, Daniel Lokshtanov, Amer Mouawad and Ramanujan M. S.
On the Parameterized Complexity of Simultaneous Deletion Problems
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha and Swagato Sanyal
A Composition Theorem for Randomized Query Complexity
Mohamed Faouzi Atig, Ahmed Bouajjani, K. Narayan Kumar and Prakash Saivasan
Verification of Asynchronous Programs with Nested Locks
Bartosz Bednarczyk and Witold Charatonik
Modulo Counting on Words and Trees
Béatrice Bérard, Serge Haddad and Engel Lefaucheux
Probabilistic Disclosure: Maximisation vs. Minimisation
Olaf Beyersdorff, Luke Hinde and Ján Pich
Reasons for Hardness in QBF Proof Systems
Amey Bhangale, Subhash Khot and Devanathan Thiruvenkatachari
An Improved Dictatorship Test with Perfect Completeness
Michael Blondin, Alain Finkel and Jean Goubault-Larrecq
Forward Analysis for WSTS, Part III: Karp-Miller Trees
Udi Boker
Rabin vs. Streett Automata
Udi Boker, Orna Kupferman and Michał Skrzypczak
How Deterministic are Good-For-Games Automata?
Florian Brandl and Telikepalli Kavitha
Popular Matchings with Multiple Partners
Joshua Brody, Joseph Boninger and Owen Kephart
Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search
Onur Cagirici, Petr Hlineny and Bodhayan Roy
On Colourability of Polygon Visibility Graphs
Yixin Cao, Yuping Ke, Yota Otachi and Jie You
Vertex Deletion Problems on Chordal Graphs
Arkadev Chattopadhyay and Nikhil Mande
A Lifting Theorem with Applications to Symmetric Functions
Joel Day, Pamela Fleischmann, Florin Manea and Dirk Nowotka
Local Patterns
Stèphane Demri, Etienne Lozes and Denis Lugiez
On Symbolic Heaps Modulo Permission Theories
Rüdiger Ehlers and Bernd Finkbeiner
Symmetric Synthesis
Alina Ene, Viswanath Nagarajan and Rishi Saket
Approximation Algorithms for Stochastic k-TSP
Bernd Finkbeiner and Paul Gölz
Synthesis in Distributed Environments
Apoorv Garg and Abhiram Ranade
Train Scheduling on a Unidirectional Path
Hugo Gimbert
On the Control of Asynchronous Automata
Elena Grigorescu, Erfan Sadeqi Azer and Samson Zhou
Streaming for Aibohphobes: Longest Palindrome with Mismatches
Guru Guruganesh and Euiwoong Lee
Understanding the Correlation Gap for Matchings
Venkatesan Guruswami and Rishi Saket
Hardness of Rainbow Coloring Hypergraphs
Yi Huang, Mano Vikash Janardhanan and Lev Reyzin
Network Construction with Ordered Constraints
Dileep Kini and Mahesh Viswanathan
Complexity of Model Checking MDPs against LTL Specifications
Andreas Krebs, Nutan Limaye and Michael Ludwig
A Unified Method for Placing Problems in Polylogarithmic Depth
Akash Kumar, Anand Louis and Madhur Tulsiani
Finding Pseudorandom Colorings of Pseudorandom Graphs
Orna Kupferman, Gal Vardi and Moshe Vardi
Flow Games
Victor Lagerkvist and Biman Roy
A Dichotomy Theorem for the Inverse Satisfiability Problem
Daniel Lokshtanov, Saket Saurabh, Roohani Sharma and Meirav Zehavi
Balanced Judicious Partition is FPT
Kuldeep S. Meel, Aditya A. Shrotri and Moshe Y. Vardi
On Hashing-Based Approaches to Approximate DNF-Counting
Jakub Michaliszyn and Jan Otop
Average Stack Cost of Buechi Pushdown Automata
Jakub Michaliszyn, Jan Otop and Piotr Wieczorek
Querying Best Paths in Graph Databases
Meghana Nasre and Prajakta Nimbhorkar
Popular Matchings with Lower Quotas
Paweł Parys
Complexity of the Diagonal Problem for Recursion Schemes
Bharatram Rangarajan
A combinatorial proof of Bass's determinant formula for the zeta function of regular graphs
Alexander Weinert
VLDL Satisfiability and Model Checking via Tree Automata