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.

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

Click here to download the slides of the talk.

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)