Skip to main content

FSTTCS 2017

37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

Indian Institute of Technology, Kanpur. December 11–15, 2017.

Check out the list of accepted papers

For authors: Download instructions for the camera-ready version

Tuesday, December 12, 2017
0800 – 0900 Registration
Invited Talk 1
0900 – 1000 Anca Muscholl (LaBRI & Université Bordeaux, France)
Automated synthesis: a distributed viewpoint
Session 1A Session 1B
1010 – 1040 A Ene, V Nagarajan & R Saket
Approximation Algorithms for Stochastic k-TSP
H Gimbert
On the Control of Asynchronous Automata
1040 – 1110 V Guruswami & R Saket
Hardness of Rainbow Coloring Hypergraphs
B Finkbeiner & P Gölz
Synthesis in Distributed Environments
1110 – 1140 Coffee break
Session 2A Session 2B
1140 – 1210 A Chattopadhyay & N Mande
A Lifting Theorem with Applications to Symmetric Functions
L Aceto, A Achilleos & A Francalanza
Monitoring for Silent Actions
1210 – 1240 A Anshu, D Gavinsky, R Jain, S Kundu, T Lee, P Mukhopadhyay, M Santha & S Sanyal
Composition Theorem for Randomized Query Complexity
S Demri, E Lozes & D Lugiez
On Symbolic Heaps Modulo Permission Theories
1240 – 1400 Lunch
Invited Talk 2
1400 – 1500 Thomas Wilke (Christian-Albrechts-Universität zu Kiel)
Backward Deterministic Finite-State Automata on Infinite Words
Session 3
1500 – 1530 O Beyersdorff, L Hinde & J Pich
Reasons for Hardness in QBF Proof Systems
1530 – 1600 Coffee Break
Session 4A Session 4B
1600 – 1630 G Guruganesh & E Lee
Understanding the Correlation Gap for Matchings
D Kini & M Viswanathan
Complexity of Model Checking MDPs against LTL Specifications
1630 – 1700 A Kumar, A Louis & M Tulsiani
Finding Pseudorandom Colorings of Pseudorandom Graphs
A Weinert
VLDL Satisfiability and Model Checking via Tree Automata
1700 – 1730 J Brody, J Boninger & O Kephart
Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search
M F Atig, A Bouajjani, K Narayan Kumar & P Saivasan
Verification of Asynchronous Programs with Nested Locks
Wednesday, December 13, 2017
Invited Talk 3
0900 – 1000 Edith Elkind (University of Oxford, UK)
Session 5A Session 5B
1010 – 1040 F Brandl & T Kavitha
Popular Matchings with Multiple Partners
U Boker
Rabin vs. Streett Automata
1040 – 1110 M Nasre & P Nimbhorkar
Popular Matchings with Lower Quotas
M Blondin, A Finkel & J Goubault-Larrecq
Forward Analysis for WSTS, Part III: Karp-Miller Trees
1110 – 1140 Coffee break
Session 6A Session 6B
1140 – 1210 P K Agarwal, K Fox & A Nath
Maintaining Reeb graphs of triangulated 2-manifolds
J Day, P Fleischmann, F Manea & D Nowotka
Local Patterns
1210 – 1240 O Cagirici, P Hlineny & B Roy
On Colourability of Polygon Visibility Graphs
R Ehlers & B Finkbeiner
Symmetric Synthesis
1240 – 1400 Lunch
Invited Talk 4
1400 – 1500 Sham Kakade (University of Washington, USA)
Session 7
1500 – 1530 O Kupferman, G Vardi & M Vardi
Flow Games
1530 – 1600 Coffee Break
Session 8A Session 8B
1600 – 1630 A Garg & A Ranade
Train Scheduling on a Unidirectional Path
P Parys
Complexity of the Diagonal Problem for Recursion Schemes
1630 – 1700 Y Huang, M V Janardhanan & L Reyzin
Network Construction with Ordered Constraints
B Bednarczyk & W Charatonik
Modulo Counting on Words and Trees
1700 – 1730 E Grigorescu, E S Azer & S Zhou
Streaming for Aibohphobes: Longest Palindrome with Mis- matches
B Bérard, S Haddad & E Lefaucheux
Probabilistic Disclosure: Maximisation vs. Minimisation
Thursday, December 14, 2017
0800 – 0900 Registration
Invited Talk 5
0900 – 1000 Devavrat Shah (MIT, USA)
Session 9A Session 9B
1010 – 1040 A Krebs, N Limaye & M Ludwig
A Unified Method for Placing Problems in Polylogarithmic Depth
U Boker, O Kupferman & M Skrzypczak
How Deterministic are Good-For-Games Automata?
1040 – 1110 Y Cao, Y Ke, Y Otachi & J You
Vertex Deletion Problems on Chordal Graphs
J Michaliszyn & J Otop
Average Stack Cost of Büchi Pushdown Automata
1110 – 1140 Coffee break
Session 10A Session 10B
1140 – 1210 D Lokshtanov, S Saurabh, R Sharma & M Zehavi
Balanced Judicious Partition is FPT
B Rangarajan
A combinatorial proof of Bass’s determinant formula for the zeta function of regular graphs
1210 – 1240 A Agrawal, R Krithika, D Lokshtanov, A Mouawad & Ramanujan M S
On the Parameterized Complexity of Simultaneous Deletion Problems
A Bhangale, S Khot & D Thiruvenkatachari
An Improved Dictatorship Test with Perfect Completeness
1240 – 1400 Lunch
Invited Talk 6
1400 – 1500 Vinod Vaikuntanathan (MIT CSAIL, USA)
Session 11
1500 – 1530 K S Meel, A A Shrotri & M Y Vardi
On Hashing-Based Approaches to Approximate DNF-Counting
1530 – 1600 Coffee Break
Session 12
1600 – 1630 V Lagerkvist & B Roy
A Dichotomy Theorem for the Inverse Satisfiability Problem
1630 – 1700 J Michaliszyn, J Otop & P Wieczorek
Querying Best Paths in Graph Databases