Skip to main content


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

December 11–13, 2019

Indian Institute of Technology Bombay

Session venues:

Wednesday, December 11, 2019
0820 – 0850 Registration
0850 – 0900 Opening
Invited Talk 1
CHAIR: Arkadev Chattopadhyay
0900 – 1000 Tim Roughgarden
How Computer Science Informs Modern Auction Design
1000 – 1015 Small break
Session A1
CHAIR: Nutan Limaye
Session B1
CHAIR: S Krishna
1015 – 1045 Diptarka Chakraborty, Debarati Das and Michal Koucky
Approximate Online Pattern Matching in Sublinear Time
Nathalie Bertrand, Patricia Bouyer and Anirban Majumdar
Concurrent parameterized games
1045 – 1115 Kanthi Sarpatwar, Baruch Schieber and Hadas Shachnai
The Preemptive Resource Allocation Problem
Thomas Brihaye, Gilles Geeraerts, Marion Hallet, Benjamin Monmege and Bruno Quoitin
Dynamics on Games: Simulation-Based Techniques and Applications to Routing
1115 – 1145 Coffee break
Session A2
CHAIR: Rohit Gurjar
Session B2
CHAIR: Alain Finkel
1145 – 1215 Prerona Chatterjee and Ramprasad Saptharishi
Constructing Faithful Homomorphisms over Fields of Finite Characteritic
Ramanathan Thinniyam Srinivasan and Georg Zetzsche
Regular Separability and Intersection Emptiness are Independent Problems
1215 – 1245 V. Arvind, Abhranil Chatterjee, Rajit Dutta and Partha Mukhopadhyay
Fast Exact Algorithms Using Hadamard Product of Polynomials
David Mestel
Widths of regular and context-free languages
1245 – 1400 Lunch break
Invited Talk 2
CHAIR: Paul Gastin
1400 – 1500 Ranko Lazić
Finkel was right: Counter-examples to several conjectures on variants of vector addition systems
1500 – 1515 Small break
Session A3
CHAIR: Kavitha Telikepalli
Session B3
CHAIR: Benjamin Monmege
1515 – 1545 Giorgio Lucarelli, Benjamin Moseley, Nguyen Thang, Abhinav Srivastav and Denis Trystram
Online Non-preemptive Scheduling to Minimize Maximum Weighted Flow-time on Related Machines
S Akshay, Hugo Bazille, Eric Fabre and Blaise Genest
Classification among Hidden Markov Models
1545 – 1615 Roy Schwartz, Mohit Singh and Sina Yazdanbod
Online and Offline Algorithms for Circuit Switch Scheduling
Benjamin Bordais, Shibashis Guha and Jean-Francois Raskin
Expected Window Mean-Payoff
1615 – 1645 Coffee break
Session A4
CHAIR: Piyush Srivastava
Session B4
CHAIR: B Srivathsan
1645 – 1715 Jan Dreier and Peter Rossmanith
Motif Counting in Preferential Attachment Graphs
Laura Bozzelli, Angelo Montanari and Adriano Peron
Taming complexity of timeline-based planning over dense temporal domains
1715 – 1745 Anand Louis and Rakesh Venkat
Planted Models for k-way Edge and Vertex Expansion
Jeffrey M. Dudek and Dror Fried
Transformations of Boolean Functions
Thursday, December 12, 2019
Invited Talk 3
CHAIR: Sanjiva Prasad
0900 – 1000 Alexandra Silva
An algebraic framework to reason about concurrency
1000 – 1015 Small break
Session A5
CHAIR: Ramprasad Saptharishi
Session B5
CHAIR: C Aiswarya
1015 – 1045 Sebastian Tavenas, Maud Szusterman, Guillaume Malod and Herve Fournier
Nonnegative Rank Measures and Monotone Algebraic Branching Programs
Salvatore La Torre and P. Madhusudan
Reachability in Concurrent Uninterpreted Programs
1045 – 1115 Srikanth Srinivasan, Utkarsh Tripathi and S Venkitesh
On the Probabilistic Degrees of Symmetric Boolean Functions
Peter Chini, Prakash Saivasan and Roland Meyer
Complexity of Liveness in Parameterized Systems
1115 – 1145 Coffee break
Session A6
CHAIR: Ruta Mehta
Session B6
CHAIR: Benedikt Bollig
1145 – 1215 Gordon Hoi, Sanjay Jain and Frank Stephan
A Fast Algorithm for Max Hamming Distance X3SAT
Emmanuel Filiot, Shibashis Guha and Nicolas Mazzocchi
Two-way Parikh Automata
1215 – 1245 Telikepalli Kavitha
Popular Roommates in Simply Exponential Time
M Praveen and Agnishom Chattopadhyay
Query Preserving Watermarking Schemes for Locally Treelike Databases
1245 – 1400 Lunch break
Invited Talk 4
CHAIR: Jaikumar Radhakrishnan
1400 – 1500 Robert Krauthgamer
Sketching Graphs and Combinatorial Optimization
1500 – 1515 Small break
Session A7
CHAIR: Srikanth Srinivasan
Session B7
CHAIR: Sunil Simon
1515 – 1545 Rahul Jain and Raghunath Tewari
An O(n¼ + ε) Space and Polynomial Algorithm for Grid Graph Reachability
Laura Bozzelli, Angelo Montanari and Adriano Peron
Interval temporal logic for visibly pushdown systems
1545 – 1615 Sanjana Kolisetty, Linh Le, Ilya Volkovich and Mihalis Yannakakis
The Complexity of Finding S-factors in Regular Graphs
Manfred Droste, Sven Dziadek and Werner Kuich
Greibach Normal Form for ω-Algebraic Systems and Weighted Simple ω-Pushdown Automata
1615 – 1645 Coffee break
Session A8
Session B8
CHAIR: Madhavan Mukund
1645 – 1715 Fabio Gadducci, Hernan Melgratti, Matteo Sammartino and Christian Roldan
A Categorical Account for the Specification of Replicated Data Type
1715 – 1830 IARCS Business Meeting
1930 – 2230 Conference Banquet
Friday, December 13, 2019
Invited Talk 5
CHAIR: Arkadev Chattopadhyay
0900 – 1000 Toniann Pitassi
Progress in Lower Bounds and Applications in Lifting
1000 – 1015 Small break
Session A9
CHAIR: Meena Mahajan
Session B9
CHAIR: Dietrich Kuske
1015 – 1045 Aditya Potukuchi
On the AC0[⊕] complexity of Andreev's Problem
Marco Kuhlmann, Andreas Maletti and Lena Katharina Schiffer
The Tree-Generative Capacity of Combinatory Categorial Grammars
1045 – 1115 Nutan Limaye, Srikanth Srinivasan and Utkarsh Tripathi
More on AC0[⊕] and Variants of the Majority Function
Alexander Rabinovich and Doron Tiferet
Degrees of Ambiguity of B├╝chi Tree Automata
1115 – 1145 Coffee break
Session A10
CHAIR: Michal Koucky
Session B10
CHAIR: M Praveen
1145 – 1215 Chetan Gupta, Rahul Jain, Vimal Raj Sharma and Raghunath Tewari
Unambiguous Catalytic Computation
Jérôme Leroux
Distance Between Mutually Reachable Petri Net Configurations
1215 – 1245 Yujin Choi, Seungjun Lee and Hee-Kap Ahn
Maximum-Area Rectangles in a Simple Polygon
Alain Finkel and Ekanshdeep Gupta
The well structured problem for Presburger counter machines
1245 – 1400 Lunch break
Invited Talk 6
CHAIR: Anca Muscholl
1400 – 1500 Karthikeyan Bhargavan
Practical Formal Methods for Real World Cryptography
1500 – 1515 Small break
Session A11
CHAIR: Jaikumar Radhakrishnan
Session B11
CHAIR: Paolo Baldan
1515 – 1545 Pallavi Jain, Lawqueen Kanesh, William Lochet, Saket Saurabh and Roohani Sharma
Exact and Approximate Digraph Bandwidth
Denis Kuperberg, Laureline Pinault and Damien Pous
Cyclic Proofs and Jumping Automata
1545 – 1615 Isolde Adler, Christophe Paul and Dimitrios Thilikos
Connected Search for a Lazy Robber
Hans Kleine Büning, Piotr Wojciechowski and K Subramani
New results on cutting plane proofs for Horn constraint systems
1615 – 1645 Coffee break
Session A12
CHAIR: Kavitha Telikepalli
Session B12
CHAIR: Bharat Adsul
1645 – 1715 Fedor Fomin, Peter Golovach and Kirill Simonov
Parameterized k-Clustering: Tractability Island
Alexandre Mansard
Boolean algebras from trace automata
1715 – 1745 Akansha Agrawal, Arindam Biswas, Edouard Bonnet, Nick Brettell, Radu Curticapean, Daniel Marx, Tillman Miltzow, Venkatesh Raman and Saket Saurabh
Parameterized Streaming Algorithms for Min-Ones d-SAT
Paolo Baldan and Alessandra Raffaeta
Minimisation of Event Structures