FSTTCS 2014
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
India International Centre, New Delhi. December 15–17, 2014.
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 | |