Skip to main content


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

India International Centre, New Delhi. December 15–17, 2014.

December 15, 2014
0800 – 0900 Registration
Invited Talk 1
CHAIR: Sandeep Sen
0900 – 1000 Umesh Vazirani
Algorithms, Games and Evolution
1000 – 1030 Coffee break
Session 1A
CHAIR: Michał Pilipczuk
Session 1B
CHAIR: K. Narayan Kumar
1030 – 1055 Ramanujan M. S and Geevarghese Philip
Vertex Exponential Algorithms for Connected f-Factors
Laurent Doyen, Line Juhl, Kim Guldstrand Larsen, Nicolas Markey and Mahsa Shirmohammadi
Synchronizing words for weighted and timed automata
1055 – 1120 Manu Basavaraju, Fedor Fomin, Petr Golovach and Saket Saurabh
Connecting Vertices by Independent Trees
Emmanuel Filiot, Raffaella Gentilini and Jean-François Raskin
Finite-Valued Weighted Automata
1120 – 1145 Archontia Giannopoulou, Daniel Lokshtanov, Saket Saurabh and Ondrej Suchy
Tree Deletion Set Has a Polynomial Kernel (but no OPTO(1) Approximation)
Emmanuel Filiot, Krishna S. and Ashutosh Trivedi
First-order definable string transformations
1145 – 1210 Konrad Kazimierz Dabrowski, Petr Golovach, Pim Van 'T Hof and Daniel Paulusma
Editing to Eulerian Graphs
Shaull Almagor, Denis Kuperberg and Orna Kupferman
Regular Sensing
1210 – 1235 Christoph Berkholz and Michael Elberfeld
Parameterized Complexity of Fixed-Variable Logics
Matthias Keil and Peter Thiemann
Symbolic Solving of Regular Expression Inequalities
1235 – 1400 Lunch
Invited Talk 2
CHAIR: Naveen Garg
1400 – 1500 Nikhil Bansal
New Developments in Iterated Rounding
1500 – 1520 Coffee Break
Session 2A
CHAIR: Amit Kumar
Session 2B
CHAIR: Ashutosh Trivedi
1520 – 1545 Adrian Bock, Yuri Faenza, Carsten Moldenhauer and Andres J. Ruiz-Vargas
Solving the stable set problem in terms of the odd cycle packing number
Hazem Torfah and Martin Zimmermann
The Complexity of Counting Models of Linear-time Temporal Logic
1545 – 1610 Konstantions Georgiou and Edward Lee
Lift & Project Systems Performing on the Partial Vertex Cover Polytope
Fu Song and Zhilin Wu
Extending temporal logics with data variable quantifications
1610 – 1635 Sonika Arora, Venkatesan Chakaravarthy, Kanika Gupta, Neelima Gupta and Yogish Sabharwal
Replica Placement on Directed Acyclic Graphs
Thomas Colcombet and Amaldev Manuel
Generalized Data Automata and Fixpoint Logic
1635 – 1700 Manoj Gupta
Maintaining (1 +ε) approximate maximum matching in an incremental bipartite graph in poly(log n, ε) update time
Claire David, Nadime Francis and Filip Murlak
Consistency of injective tree patterns
December 16, 2014
Invited Talk 3
CHAIR: Kamal Lodaya
0900 – 1000 Orna Kupferman
Properties and Utilization of Capacitated Automata
1000 – 1030 Coffee break
Session 3A
CHAIR: Kavitha Telikepalli
Session 3B
CHAIR: Sunil Simon
1030 – 1055 Gonzalo Navarro, Rajeev Raman and Srinivasa Rao Satti
Asymptotically Optimal Encodings for Range Selection
Patricia Bouyer, Nicolas Markey and Daniel Stan
Mixed Nash Equilibria in Concurrent Games
1055 – 1120 Roberto Grossi, Giulia Menconi, Nadia Pisanti, Roberto Trani and Søren Vind
Output-Sensitive Pattern Extraction in Sequences
Paul Hunter and Jean-François Raskin
Quantitative games with interval objectives
1120 – 1145 Sariel Har-Peled and Nirman Kumar
Robust Proximity Search for Balls using Sublinear Space
Thomas Colcombet, Nathanaël Fijalkow and Florian Horn
Playing Safe
1145 – 1210 Amnon Ta-Shma and Efraim Gelman
The Benes network is q(q-1)/2n almost q-wise independent
Flavio Leonardo Cavalcanti de Moura, Delia Kesner and Mauricio Ayala-Rincon
Metaconfluence of Calculi with Explicit Substitutions at a Distance
1210 – 1235 Dmitry Chistikov
Notes on Counting with Finite Machines
Paolo Baldan, Filippo Bonchi, Henning Kerstan and Barbara König
Behavioral Metrics via Functor Lifting
1235 – 1400 Lunch
Invited Talk 4
CHAIR: Venkatesh Raman
1400 – 1500 Martin Grohe
Colour Refinement: A simple partitioning algorithm with applications from Graph Isomorphism Testing to Machine Learning
1500 – 1520 Coffee Break
Session 4
CHAIR: S P Suresh
1520 – 1545 Nathalie Bertrand, Serge Haddad and Engel Lefaucheux
Foundation of Diagnosis and Predictability in Probabilistic Systems
1545 – 1610 Thomas Henzinger, Jan Otop and Roopsha Samanta
Lipschitz Robustness of Finite-state Transducers
1615 – 1700 IARCS Business Meeting
1900 – 2200 Conference Banquet
December 17, 2014
Invited Talk 5
CHAIR: Rahul Santhanam
0900 – 1000 Ryan Williams
Unexpected Applications of Circuit Complexity to Algorithm Design
1000 – 1030 Coffee break
Session 5A
CHAIR: Jayalal Sarma
Session 5B
CHAIR: Sanjiva Prasad
1030 – 1055 Debasis Mandal, A Pavan and Rajeswari Venugopalan
Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis
Rohit Chadha, Umang Mathur and Stefan Schwoon
Computing Information Flow Using Symbolic Model-Checking
1055 – 1120 Danny Hucke, Markus Lohrey and Eric Nöth
Constructing small tree grammars and small circuits for formulas
Fabrizio Biondi, Axel Legay, Pasquale Malacaria, Bo Friis Nielsen and Andrzej Wasowski
Information Leakage of Non-Terminating Processes
1120 – 1145 Ryan O'Donnell and A. C. Cem Say
One time-traveling bit is as good as logarithmically many
Jean-François Raskin and Ocan Sankur
Multiple-Environment Markov Decision Processes
1145 – 1210 Hartmut Klauck and Supartha Podder
New Bounds for the Garden-Hose Model
Franck Cassez, Christian Müller and Karla Burnett
Summary-Based Inter-Procedural Analysis via Modular Trace Refinement
1210 – 1235 Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre and Nitin Saurabh
Homomorphism polynomials complete for VP
Mary Southern and Kaustuv Chaudhuri
A Two-Level Logic Approach to Reasoning about Typed Specification Languages
1235 – 1400 Lunch
Invited Talk 6
CHAIR: Madhavan Mukund
1400 – 1500 Paul Gastin
Reasoning about Distributed Systems: WYSIWYG
1500 – 1515 Coffee Break
Session 6A
CHAIR: Srikanth Srinivasan
Session 6B
CHAIR: S. Akshay
1515 – 1540 Taolue Chen and Tingting Han
On the Complexity of Computing Maximum Entropy for Markovian Models
Mohamed Faouzi Atig, Ahmed Bouajjani, K. Narayan Kumar and Prakash Saivasan
On Bounded Reachability Analysis of Shared Memory Systems
1540 – 1605 Diptarka Chakraborty, A Pavan, Raghunath Tewari, N. V. Vinodchandran and Lin Yang
New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs
Benedikt Bollig, Paul Gastin and Akshay Kumar
Parameterized Communicating Automata: Complementation and Model Checking
1605 – 1630 Anant Dhayal, Jayalal Sarma and Saurabh Sawlani
Polynomial Min/Max-weighted Reachability is in Unambiguous Logspace
Anca Muscholl and Igor Walukiewicz
Distributed synthesis for acyclic architectures
1630 – 1655 Parosh Aziz Abdulla, Mohamed Faouzi Atig, Ahmet Kara and Othmane Rezine
Verification of Dynamic Register Automata
1655 – 1700 Closing Remarks