FSTTCS 2015
35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Indian Institute of Science, Bangalore. December 16–18, 2015.
35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Indian Institute of Science, Bangalore. December 16–18, 2015.
Keshav Goyal (IIT Delhi) and Tobias Mömke (Saarland)
Robust Reoptimization of Steiner Trees
Chung-Kil Hur (Seoul National Univ.), Aditya Nori (MSR India), Sriram Rajamani (MSR India) and Selva Samuel (MSR India)
A Provably Correct Sampler for Probabilistic Programs
Fedor Fomin (U. Bergen), Petr Golovach (U. Bergen),
Nikolay Karpov (PDMI RAS, Russia) and Alexander Kulikov (PDMI RAS, Russia)
Parameterized Complexity of Secluded Connectivity Problems
Sudeshna Kolay (IMSc) and Fahad Panolan (IMSc)
Parameterized Algorithms for Deletion to (r,l)-graphs
Thomas Brihaye (Univ. de Mons), Gilles Geeraerts (Univ. libre de Bruxelles), Axel Haddad (Univ. de Mons), Benjamin Monmege (Univ. libre de Bruxelles), Guillermo Perez (Univ. libre de Bruxelles) and Gabriel Renault (Univ. de Mons)
Quantitative Games under Failures
Arnab Ganguly (Lousiana State Univ.), Sudip Biswas (Lousiana State Univ.), Rahul Shah (Lousiana State Univ.) and Sharma V. Thankachan (Georgia Tech)
Forbidden Extension Queries
Jennifer Iglesias (CMU), Rajmohan Rajaraman
(Northeastern), Ravi Sundaram (Northeastern) and R
Ravi (CMU)
Rumors over Radio, Wireless, and Telephone
Shaull Almagor (Hebrew Univ.), Denis Kuperberg (IRIT/ONERA, Toulouse) and Orna Kupferman (Hebrew Univ.)
The Sensing Cost of Monitoring and Synthesis
Anamitra Roy Choudhury (IBM Research India), Syamantak Das (IIT Delhi) and Amit Kumar (IIT Delhi)
Minimizing weighted $\ell_p$-norm of flow-time in the rejection model
Guy Avni (Hebrew Univ.), Orna Kupferman (Hebrew Univ.) and Tami Tamir (IDC, Israel)
Congestion Games with Multisets of Resources and Applications in Synthesis
Prachi Goyal (IISc), Pranabendu Misra (IMSc), Fahad
Panolan (IMSc), Geevarghese Philip (MPI-I,
Saarbrucken) and Saket Saurabh (IMSc)
Finding Even Subgraphs Even Faster
Ashish Chiplunkar (IIT Bombay) and Sundar Vishwanathan (IIT Bombay)
Approximating the Regular Graphic TSP in near Linear Time
Romain Demangeon (Univ. Pierre et Marie Curie) and Nobuko Yoshida (Imperial College, London)
On the Expressiveness of Multiparty Session Types
Dietmar Berwanger (LSV, CNRS and Univ. Paris-Saclay) and Marie Van Den Bogaard (LSV, CNRS and Univ. Paris-Saclay)
Games with Delays. A Frankenstein Approach
Hal Daume Iii (Univ. Maryland), Samir Khuller (Univ. Maryland), Manish Purohit (Univ. Maryland) and Gregory Sanders (Univ. Maryland)
On Correcting Inputs: Inverse Optimization for Online Structured Prediction
Sagnik Mukhopadhyay (TIFR) and Swagato Sanyal (TIFR)
Towards Better Separation between Deterministic and Randomized Query Complexity
Manindra Agrawal (IIT Kanpur), Diptarka Chakraborty
(IIT Kanpur), Debarati Das (Charles Univ., Prague) and
Satyadev Nandakumar (IIT Kanpur)
Dimension, Pseudorandomness and Extraction of Pseudorandomness
Lorenzo Clemente (Univ. Warsaw), Paweł Parys (Univ. Warsaw), Sylvain Salvati (LaBRI) and Igor Walukiewicz (CNRS, LaBRI)
Ordered Tree-Pushdown Systems
Félix Baschenis (LaBRI), Olivier Gauwin (LaBRI), Anca Muscholl (LaBRI) and Gabriele Puppis (LaBRI)
One-way definability of sweeping transducers
Arijit Bishnu (ISI, Kolkata), Amit Chakrabarti (Dartmouth), Subhas Nandy (ISI, Kolkata) and Sandeep Sen (IIT Delhi)
On Density, Threshold and Emptiness Queries for Intervals in the Streaming Model
Henryk Michalewski (Univ. Warsaw) and Matteo Mio (CNRS/ENS-Lyon)
On the Problem of Computing the Probability of Regular Sets of Trees
Vladimir Braverman (John Hopkins), Harry Lang (John
Hopkins), Keith Levin (John Hopkins) and Morteza
Monemizadeh (Charles Univ, Prague)
Clustering on Sliding Windows in Polylogarithmic Space
Thomas Brihaye (Univ. de Mons), Gilles Geeraerts (Univ. libre de Bruxelles), Axel Haddad (Univ. de Mons), Engel Lefaucheux (ENS Cachan) and Benjamin Monmege (Univ. libre de Bruxelles)
Simple Priced Timed Games Are Not That Simple
Thomas Weidner (Univ. Leipzig)
Probabilistic Regular Expressions and MSO Logic on Finite Trees
Karthekeyan Chandrasekaran (UIUC), Venkata Gandikota (Purdue) and Elena Grigorescu (Purdue)
Deciding Orthogonality in Construction-A Lattices
Vincent Cheval (Univ. Kent), Veronique Cortier (CNRS, Loria) and Eric Le Morvan (CNRS, Loria)
Secure refinements of communication channels
Till Fluschnik (TU Berlin), Stefan Kratsch (Univ. Bonn), Rolf Niedermeier (TU Berlin) and Manuel Sorge (TU Berlin)
The Parameterized Complexity of the Minimum Shared Edges Problem
Nikhil Balaji (CMI), Samir Datta (CMI) and Venkatesh Ganesan (BITS Pilani)
Counting Euler Tours in Undirected Bounded Treewidth Graphs
Parosh Aziz Abdulla (Uppsala Univ.), Mohamed Faouzi
Atig (Uppsala Univ.), Roland Meyer
(Univ. Kaiserslautern) and Mehdi Seyed Salehi
(Univ. Ottawa)
What’s Decidable about Availability Languages
David Cachera (ENS, Rennes), Uli Fahrenberg (IRISA/INRIA, Rennes) and Axel Legay (IRISA/INRIA, Rennes)
An ω-Algebra for Real-Time Energy Problems
David Basin (ETH Zurich), Felix Klaedtke (NEC Europe) and Eugen Zalinescu (ETH Zurich)
Failure-aware Runtime Verification of Distributed Systems
Patricia Bouyer (LSV, CNRS & ENS Cachan), Patrick Gardy (LSV, CNRS & ENS Cachan) and Nicolas Markey (LSV, CNRS & ENS Cachan)
Weighted strategy logic with Boolean goals over one-counter games
Arindam Khan (Georgia Tech.) and Mohit Singh (MSR Redmond)
On Weighted Bipartite Edge Coloring
Magnus M. Halldorsson (Reykjavik Univ.) and Tigran Tonoyan (Reykjavik Univ.)
The Price of Local Power Control in Wireless Scheduling
Leonard J. Schulman (Caltech) and Vijay V. Vazirani (Georgia Tech.)
Allocation of Divisible Goods under Lexicographic Preferences
Sepehr Assadi (UPenn), Sanjeev Khanna (UPenn), Yang Li (UPenn) and Val Tannen (UPenn)
Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches
Daniel J. Fremont (Berkeley), Alexandre Donzé (Berkeley), Sanjit A. Seshia (Berkeley) and David Wessel (Berkeley)
Control Improvisation
John M. Hitchcock (Univ. Wyoming) and A. Pavan (Iowa State Univ.)
On the NP-Completeness of the Minimum Circuit Size Problem
Lukas Fleischer (Univ. Stuttgart) and Manfred Kufleitner (Univ. Stuttgart)
Efficient algorithms for morphisms over omega-regular languages
Prateek Karandikar (LIAFA) and Philippe Schnoebelen (LSV, CNRS & ENS Cachan)
Decidability in the logic of subsequences and supersequences
Shibashis Guha (IIT Delhi), Krishna S. (IIT Bombay), Lakshmi Manasa (IIT Bombay) and Ashutosh Trivedi (IIT Bombay)
Revisiting Robustness in Priced Timed Games
Thomas Colcombet (CNRS) and Amaldev Manuel (LIAFA)
Fragments of Fixpoint Logic on Data Words