Skip to main content


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

Indian Institute of Science, Bangalore. December 16–18, 2015.

Venues (see here for more info):

16 December, 2015
0800 – 0900 Registration (MRC Auditorium)
Invited Talk 1 (MRC Auditorium)
CHAIR: Prahladh Harsha
0900 – 1000 Moses Charikar
Bypassing Worst Case Analysis: Tensor Decomposition and Clustering [ slides (pptx, 3.6MB) ]
1000 – 1030 Coffee break (MRC Auditorium)
Session 1A (CSA 117)
CHAIR: Amit Deshpande
Session 1B (MRC Auditorium)
CHAIR: Roland Meyer
1030 – 1100 Keshav Goyal and Tobias Mömke
Robust Reoptimization of Steiner Trees
Patricia Bouyer, Patrick Gardy and Nicolas Markey
Weighted strategy logic with Boolean goals over one-counter games
1100 – 1130 Anamitra Roy Choudhury, Syamantak Das and Amit Kumar
Minimizing weighted $\ell_p$-norm of flow-time in the rejection model
Prateek Karandikar and Philippe Schnoebelen
Decidability in the logic of subsequences and supersequences
1130 – 1200 Hal Daume Iii, Samir Khuller, Manish Purohit and Gregory Sanders
On Correcting Inputs: Inverse Optimization for Online Structured Prediction
Thomas Colcombet and Amaldev Manuel
Fragments of Fixpoint Logic on Data Words
1200 – 1230 Sepehr Assadi, Sanjeev Khanna, Yang Li and Val Tannen
Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches
Lukas Fleischer and Manfred Kufleitner
Efficient algorithms for morphisms over omega-regular languages
1230 – 1400 Lunch (CSA Garden)
Invited Talk 2 (MRC Auditorium)
CHAIR: Madhavan Mukund
1400 – 1500 Ahmed Bouajjani
Checking Correctness of Concurrent Objects: Tractable Reductions to Reachability [ slides (pdf, 0.7MB) ]
1500 – 1530 Coffee Break (MRC Auditorium)
Session 2A (CSA 117)
CHAIR: Kavitha Telikepalli
Session 2B (MRC Auditorium)
CHAIR: S P Suresh
1530 – 1600 Ashish Chiplunkar and Sundar Vishwanathan
Approximating the Regular Graphic TSP in near Linear Time
Lorenzo Clemente, Pawel Parys, Sylvain Salvati and Igor Walukiewicz
Ordered Tree-Pushdown Systems
1600 – 1630 Arindam Khan and Mohit Singh
On Weighted Bipartite Edge Coloring
Félix Baschenis, Olivier Gauwin, Anca Muscholl and Gabriele Puppis
One-way definability of sweeping transducers
1630 – 1700 Karthekeyan Chandrasekaran, Venkata Gandikota and Elena Grigorescu
Deciding Orthogonality in Construction-A Lattices
Parosh Aziz Abdulla, Mohamed Faouzi Atig, Roland Meyer and Mehdi Seyed Salehi
What's Decidable about Availability Languages
17 December, 2015
Invited Talk 3 (MRC Auditorium)
CHAIR: S Akshay
0900 – 1000 James Worrell
Reachability Problems for Continuous Linear Dynamical Systems [ slides (pdf, 0.8MB) ]
1000 – 1030 Coffee break (MRC Auditorium)
Session 3A (CSA 117)
CHAIR: Arnab Bhattacharyya
Session 3B (MRC Auditorium)
CHAIR: Parosh Abdulla
1030 – 1100 Sagnik Mukhopadhyay and Swagato Sanyal
Towards Better Separation between Deterministic and Randomized Query Complexity
Shibashis Guha, Krishna S., Lakshmi Manasa and Ashutosh Trivedi
Revisiting Robustness in Priced Timed Games
1100 – 1130 Manindra Agrawal, Diptarka Chakraborty, Debarati Das and Satyadev Nandakumar
Dimension, Pseudorandomness and Extraction of Pseudorandomness
Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Engel Lefaucheux and Benjamin Monmege
Simple Priced Timed Games Are Not That Simple
1130 – 1200 John M. Hitchcock and A. Pavan
On the NP-Completeness of the Minimum Circuit Size Problem
Thomas Brihaye, Gilles Geeraerts, Axel Haddad, Benjamin Monmege, Guillermo Perez and Gabriel Renault
Quantitative Games under Failures
1200 – 1230 Nikhil Balaji, Samir Datta and Venkatesh Ganesan
Counting Euler Tours in Undirected Bounded Treewidth Graphs
Dietmar Berwanger and Marie Van Den Bogaard
Games with Delays. A Frankenstein Approach
1230 – 1400 Lunch (CSA Garden)
Invited Talk 4 (MRC Auditorium)
CHAIR: Jaikumar Radhakrishnan
1400 – 1500 Boaz Barak
Convexity, Bayesianism, and the quest towards Optimal Algorithms [ slides (pptx, 2.5MB) ]
1500 – 1530 Coffee Break (MRC Auditorium)
Session 4A (CSA 117)
CHAIR: Arkadev Chattopadhyay
Session 4B (MRC Auditorium)
CHAIR: Deepak D'Souza
1530 – 1600 Arnab Ganguly, Sudip Biswas, Rahul Shah and Sharma V. Thankachan
Forbidden Extension Queries
Guy Avni, Orna Kupferman and Tami Tamir
Congestion Games with Multisets of Resources and Applications in Synthesis
1600 – 1630 Arijit Bishnu, Amit Chakrabarti, Subhas Nandy and Sandeep Sen
On Density, Threshold and Emptiness Queries for Intervals in the Streaming Model
Shaull Almagor, Denis Kuperberg and Orna Kupferman
The Sensing Cost of Monitoring and Synthesis
1630 – 1700 Vladimir Braverman, Harry Lang, Keith Levin and Morteza Monemizadeh
Clustering on Sliding Windows in Polylogarithmic Space
David Cachera, Uli Fahrenberg and Axel Legay
An omega-Algebra for Real-Time Energy Problems
1700 – 1800 IARCS Business Meeting (MRC Auditorium)
1900 – 2200 Conference Banquet (Jayamahal Palace Hotel)
18 December, 2015
Invited Talk 5 (MRC Auditorium)
CHAIR: Amit Deshpande
0900 – 1000 Ankur Moitra
Beyond Matrix Completion [ slides (pdf, 3.4MB) ]
1000 – 1030 Coffee break (MRC Auditorium)
Session 5A (CSA 117)
CHAIR: Jaikumar Radhakrishnan
Session 5B (MRC Auditorium)
CHAIR: S Akshay
1030 – 1100 Fedor Fomin, Petr Golovach, Nikolay Karpov and Alexander Kulikov
Parameterized Complexity of Secluded Connectivity Problems
Daniel J. Fremont, Alexandre Donzé, Sanjit A. Seshia and David Wessel
Control Improvisation
1100 – 1130 Sudeshna Kolay and Fahad Panolan
Parameterized Algorithms for Deletion to (r,l)-graphs
Chung-Kil Hur, Aditya Nori, Sriram Rajamani and Selva Samuel
A Provably Correct Sampler for Probabilistic Programs
1130 – 1200 Prachi Goyal, Pranabendu Misra, Fahad Panolan, Geevarghese Philip and Saket Saurabh
Finding Even Subgraphs Even Faster
Henryk Michalewski and Matteo Mio
On the Problem of Computing the Probability of Regular Sets of Trees
1200 – 1230 Till Fluschnik, Stefan Kratsch, Rolf Niedermeier and Manuel Sorge
The Parameterized Complexity of the Minimum Shared Edges Problem
Thomas Weidner
Probabilistic Regular Expressions and MSO Logic on Finite Trees
1230 – 1400 Lunch (CSA Garden)
Invited Talk 6 (MRC Auditorium)
CHAIR: G Ramalingam
1400 – 1500 Suresh Jagannathan
Relational Refinement Types for Higher-Order Shape Transformers [ slides (pdf, 0.8MB) ]
1500 – 1530 Coffee Break (MRC Auditorium)
Session 6A (CSA 117)
CHAIR: Prahladh Harsha
Session 6B (MRC Auditorium)
CHAIR: G Ramalingam
1530 – 1600 Jennifer Iglesias, Rajmohan Rajaraman, Ravi Sundaram and R Ravi
Rumors over Radio, Wireless, and Telephone
Romain Demangeon and Nobuko Yoshida
On the Expressiveness of Multiparty Session Types
1600 – 1630 Magnus M. Halldorsson and Tigran Tonoyan
The Price of Local Power Control in Wireless Scheduling
Vincent Cheval, Veronique Cortier and Eric Le Morvan
Secure refinements of communication channels
1630 – 1700 Leonard J. Schulman and Vijay V. Vazirani
Allocation of Divisible Goods under Lexicographic Preferences
David Basin, Felix Klaedtke and Eugen Zalinescu
Failure-aware Runtime Verification of Distributed Systems
1705 – 1710 Closing Remarks