Skip to main content

FSTTCS 2018

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

December 10–14, 2018

School of Engineering and Applied Science
Ahmedabad University

Click here for the FSTTCS'18 proceedings.

Conference Programme

Tuesday, December 11, 2018

0800 onwards Registration (Outside Auditorium, GICT Building)
0850 Welcome address by Prof. Pankaj Chandra, Vice Chancellor, Ahmedabad University (Auditorium, GICT Building)
0900 – 1000 Invited Talk 1 (Auditorium, GICT Building)
Santosh Vempala
Continuous Algorithms
CHAIR: Sumit Ganguly
1000 – 1015 Tea break (Outside Auditorium, GICT Building)
Session 1A (Room No. 106, First Floor, GICT Building)
CHAIR: Meena Mahajan 		Session 1B (Room No. 107, First Floor, GICT Building)
CHAIR: Madhavan Mukund
1015 – 1045 Ramprasad Saptharishi and Anamay Tengse
Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees 		Alain Finkel, Jérôme Leroux and Grégoire Sutre
Reachability for Two-Counter Machines with One Test and One Reset
1045 – 1115 V. Arvind, Abhranil Chatterjee, Rajit Datta and Partha Mukhopadhyay
Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators 		Vincent Penelle, Sylvain Salvati and Grégoire Sutre
On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems
1115 – 1145 Tea break (Airport Area, Outside Room No. 107, GICT Building)
Session 2A (Room No. 106, First Floor, GICT Building)
CHAIR: Deepanjan Kesh 		Session 2B (Room No. 107, First Floor, GICT Building)
CHAIR: K Narayan Kumar
1145 – 1215 Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli and Srikanth Srinivasan
On the Probabilistic Degree of OR over the Reals 		Udi Boker and Karoliina Lehtinen
On The Way to Alternating Weak Automata
1215 – 1245 Elazar Goldenberg and Karthik C. S.
Towards a General Direct Product Testing Theorem 		Faried Abu Zaid
Uniformly Automatic Classes of Finite Structures
1245 – 1400 Lunch (Airport Area, Outside Room No. 107, GICT Building)
1400 – 1500 Invited Talk 2 (Auditorium, GICT Building)
A. Prasad Sistla
Model Checking Randomized Security Protocols
CHAIR: Paritosh Pandya
Session 3A (Room No. 106, First Floor, GICT Building)
CHAIR: Yossi Azar 		Session 3B (Room No. 107, First Floor, GICT Building)
CHAIR: Paul Gastin
1530 – 1600 Sapna Grover, Neelima Gupta, Samir Khuller and Aditya Pancholi
Constant factor Approximation Algorithm for Uniform Hard Capacitated Knapsack Median Problem 		Sougata Bose, Anca Muscholl , Vincent Penelle and Gabriele Puppis
Origin-equivalence of Two-way Word Transducers is in PSPACE
1600 – 1630 Manisha Bansal, Naveen Garg and Neelima Gupta
A 5-approximation for Universal Facility Location 		Emmanuel Filiot, Olivier Gauwin , Nathan Lhote and Anca Muscholl
On Canonical Models for Rational Functions over Infinite Words
1630 – 1700 Amy Babay, Michael Dinitz and Zeyu Zhang.
Characterizing Demand Graphs for r (Fixed-Parameter) Shallow-Light Steiner Network 		Janusz Schmude, Adrien Boiret and Radosław Piórkowski
The “Hilbert Method” for Solving Transducer Equivalence Problems

Wednesday, December 12, 2018

0900 – 1000 Invited Talk 3 (Auditorium, GICT Building)
Rupak Majumdar
Random Testing for Distributed Systems with Theoretical Guarantees
CHAIR: Deepak D'Souza
1000 – 1015 Tea break (Outside Auditorium, GICT Building)
Session 4A (Room No. 106, First Floor, GICT Building)
CHAIR: Umang Bhaskar 		Session 4B (Room No. 107, First Floor, GICT Building)
CHAIR: Kamal Lodaya
1015 – 1045 Balthazar Bauer, Jevgēnijs Vihrovs and Hoeteck Wee
On the Inner Product Predicate and a Generalization of Matching Vector Families 		Thomas Place and Marc Zeitoun
The Complexity of Separation for Levels in Concatenation Hierarchies
1045 – 1115 Deepanjan Kesh
Space Complexity of Two Adaptive Bitprobe Schemes Storing Three Elements 		Faried Abu Zaid and Chris Köcher
The Cayley-Graph of the Queue Monoid: Logic and Decidability
1115 – 1145 Tea break (Airport Area, Outside Room No. 107, GICT Building)
Session 5A (Room No. 106, First Floor, GICT Building)
CHAIR: Yossi Azar 		Session 5B (Room No. 107, First Floor, GICT Building)
CHAIR: Alain Finkel
1145 – 1215 Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer and Kurt Mehlhorn
On Fair Division for Indivisible Items 		Pierre Ganty and Elena Gutiérrez
The Parikh Property for Weighted Context-Free Grammars
1215 – 1245 Bhaskar Ray Chaudhury and Kurt Mehlhorn
Combinatorial Algorithms for General Linear Arrow-Debreu Markets 		Kazuyuki Asada and Naoki Kobayashi
Lambda-Definable Order-3 Tree Functions are Well-Quasi-Ordered
1245 – 1400 Lunch (Airport Area, Outside Room No. 107, GICT Building)
Session 6A (Room No. 106, First Floor, GICT Building)
CHAIR: Sumit Ganguly 		Session 6B (Room No. 107, First Floor, GICT Building)
CHAIR: R. Ramanujam
1400 – 1430 Sumedh Tirodkar
Deterministic Algorithms for Maximum Matching on General Graphs in the Semi-Streaming Model 		Furio Honsell, Luigi Liquori , Claude Stolze and Ivan Scagnetto
The ∆-framework
1430 – 1500 Karl Bringmann and Bhaskar Ray Chaudhury
Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS 		Alessio Mansutti
Extending Propositional Separation Logic for Robustness Properties
1500 – 1530 Tea break (Airport Area, Outside Room No. 107, GICT Building)
Session 7A (Room No. 106, First Floor, GICT Building)
CHAIR: Neeldhara Misra 		Session 7B (Room No. 107, First Floor, GICT Building)
CHAIR: S.P. Suresh
1530 – 1600 Mohsen Alambardar Meybodi, Fedor V. Fomin, Amer E. Mouawad and Fahad Panolan
On the parameterized complexity of [1,j]-domination problems 		David Baelde, Anthony Lick and Sylvain Schmitz
A Hypersequent Calculus with Clusters for Tense Logic over Ordinals
1600 – 1630 Pranabendu Misra, Roohani Sharma, Saket Saurabh and Meirav Zehavi
Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number 		Anantha Padmanabha, R. Ramanujam and Yanjing Wang
Bundled Fragments of First Order Modal Logic: (Un)decidability
1630 – 1700 Junjie Luo, Hendrik Molter, André Nichterlein and Rolf Niedermeier
Parameterized Dynamic Cluster Editing 		Beatrice Berard, Stefan Haar and Loic Helouet
Hyper Partial Order Logic
1710 IARCS Business Meeting (Auditorium, GICT Building)
1800 Departure for banquet at Vishalla from the conference venue.

Thursday, December 13, 2018

0900 – 1000 Invited Talk 4 (Auditorium, GICT Building)
Ola Svensson
Algorithms for the Asymmetric Traveling Salesman Problem
CHAIR: Meena Mahajan
1000 – 1015 Tea Break (Outside Auditorium, GICT Building)
Session 8A (Room No. 106, First Floor, GICT Building)
CHAIR: Neeldhara Misra 		Session 8B (Room No. 107, First Floor, GICT Building)
CHAIR: S.N. Krishna
1015 – 1045 Ágnes Cseh and Telikepalli Kavitha
Popular Matchings in Complete Graphs 		Marc Bagno and Denis Kuperberg
Büchi Good-for-Games Automata are Efficiently Recognizable
1045 – 1115 Samir Datta, Siddharth Iyer, Raghav Kulkarni and Anish Mukherjee
Shortest k-Disjoint Paths via Determinants 		Stephane Le Roux, Arno Pauly and Mickael Randour
Extending Finite-memory Determinacy to Boolean Combinations of Winning Conditions
1115 – 1145 Tea break (Airport Area, Outside Room No. 107, GICT Building)
Session 9A (Room No. 106, First Floor, GICT Building)
CHAIR: Kavitha Telikepalli 		Session 9B (Room No. 107, First Floor, GICT Building)
CHAIR: R. Ramanujam
1145 – 1215 Siddhesh Chaubal and Anna Gal
New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity 		Damien Busatto-Gaston, Benjamin Monmege and Pierre-Alain Reynier
Symbolic Approximation of Weighted Timed Games
1215 – 1245 Umang Bhaskar and Abheek Ghosh
On the Welfare of Cardinal Voting Mechanisms 		Gilles Geeraerts, Shibashis Guha and Jean-Francois Raskin
Safe and Optimal Scheduling for Hard and Soft Tasks
1245 – 1400 Lunch (Airport Area, Outside Room No. 107, GICT Building)
Session 10A (Room No. 106, First Floor, GICT Building)
CHAIR: Kavitha Telikepalli 		Session 10B (Room No. 107, First Floor, GICT Building)
CHAIR: B. Srivathsan
1400 – 1430 Markus Bläser, Balagopal Komarath and Karteek Sreenivasaiah
Graph Pattern Polynomials 		Parosh Abdulla, Mohamed Faouzi Atig, Krishna S and Shaan Vaidya
Verification of Timed Asynchronous Programs
1430 – 1500 Swaroop N P and Vikram Sharma
Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model 		Alexandre Debant, Stephanie Delaune and Cyrille Wiedling
Proving Physical Proximity using Symbolic Models
1500 – 1530 Concluding Remarks (Room No. 107) and Tea (Airport Area, Outside Room No. 107, GICT Building)