FSTTCS 2015 December 16-18, 2015 - Bangalore, India

35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)



Prahladh Harsha and G. Ramalingam (Eds.)
ISBN 978-3-939897-97-2, LIPICS Vol. 45 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 22 MB)
Search Publication Server

Authors
  • Abdulla, Parosh Aziz
  • Agrawal, Manindra
  • Almagor, Shaull
  • Assadi, Sepehr
  • Atig, Mohamed Faouzi
  • Avni, Guy
  • Balaji, Nikhil
  • Barak, Boaz
  • Baschenis, Félix
  • Basin, David
  • Berwanger, Dietmar
  • Bishnu, Arijit
  • Biswas, Sudip
  • Bouajjani, Ahmed
  • Bouyer, Patricia
  • Braverman, Vladimir
  • Brihaye, Thomas
  • Cachera, David
  • Chakrabarti, Amit
  • Chakraborty, Diptarka
  • Chandrasekaran, Karthekeyan
  • Charikar, Moses S.
  • Cheval, Vincent
  • Chiplunkar, Ashish
  • Clemente, Lorenzo
  • Colcombet, Thomas
  • Cortier, Véronique
  • Das, Debarati
  • Das, Syamantak
  • Datta, Samir
  • Daumé III, Hal
  • Demangeon, Romain
  • Donzé, Alexandre
  • Emmi, Michael
  • Enea, Constantin
  • Fahrenberg, Uli
  • Fleischer, Lukas
  • Fluschnik, Till
  • Fomin, Fedor V.
  • Fremont, Daniel J.
  • Gandikota, Venkata
  • Ganesan, Venkatesh
  • Ganguly, Arnab
  • Gardy, Patrick
  • Gauwin, Olivier
  • Geeraerts, Gilles
  • Golovach, Petr A.
  • Goyal, Keshav
  • Goyal, Prachi
  • Grigorescu, Elena
  • Guha, Shibashis
  • Haddad, Axel
  • Halldórsson, Magnús M.
  • Hamza, Jad
  • Harsha, Prahladh
  • Hitchcock, John M.
  • Hur, Chung-Kil
  • Iglesias, Jennifer
  • Jagannathan, Suresh
  • Karandikar, Prateek
  • Karpov, Nikolay
  • Khan, Arindam
  • Khanna, Sanjeev
  • Khuller, Samir
  • Klaedtke, Felix
  • Kolay, Sudeshna
  • Kratsch, Stefan
  • Krishna, Shankara Narayanan
  • Kufleitner, Manfred
  • Kulikov, Alexander S.
  • Kumar, Amit
  • Kuperberg, Denis
  • Kupferman, Orna
  • Lang, Harry
  • Lefaucheux, Engel
  • Legay, Axel
  • le Morvan, Eric
  • Levin, Keith
  • Li, Yang
  • Manasa, Lakshmi
  • Manuel, Amaldev
  • Markey, Nicolas
  • Meyer, Roland
  • Michalewski, Henryk
  • Mio, Matteo
  • Misra, Pranabendu
  • Moitra, Ankur
  • Mömke, Tobias
  • Monemizadeh, Morteza
  • Monmege, Benjamin
  • Mukhopadhyay, Sagnik
  • Muscholl, Anca
  • Nandakumar, Satyadev
  • Nandy, Subhas C.
  • Niedermeier, Rolf
  • Nori, Aditya V.
  • Panolan, Fahad
  • Parys, Pawel
  • Pavan, A.
  • Pérez, Guillermo A.
  • Philip, Geevarghese
  • Puppis, Gabriele
  • Purohit, Manish
  • Rajamani, Sriram K.
  • Rajaraman, Rajmohan
  • Ramalingam, G.
  • Ravi, R.
  • Renault, Gabriel
  • Roy Choudhury, Anamitra
  • Salvati, Sylvain
  • Samuel, Selva
  • Sanders, Gregory
  • Sanyal, Swagato
  • Saurabh, Saket
  • Schnoebelen, Philippe
  • Schulman, Leonard J.
  • Sen, Sandeep
  • Seshia, Sanjit A.
  • Seyed Salehi, Mehdi
  • Shah, Rahul
  • Singh, Mohit
  • Sorge, Manuel
  • Sundaram, Ravi
  • Tamir, Tami
  • Tannen, Val
  • Thankachan, Sharma V.
  • Tonoyan, Tigran
  • Trivedi, Ashutosh
  • van den Bogaard, Marie
  • Vazirani, Vijay V.
  • Vishwanathan, Sundar
  • Walukiewicz, Igor
  • Weidner, Thomas
  • Wessel, David
  • Worrell, James
  • Yoshida, Nobuko
  • Zalinescu, Eugen
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Harsha, Prahladh ; Ramalingam, G.

    Abstract | Document (362 KB) | BibTeX

    Bypassing Worst Case Analysis: Tensor Decomposition and Clustering (Invited Talk)
    Authors: Charikar, Moses S.

    Abstract | Document (205 KB) | BibTeX

    Checking Correctness of Concurrent Objects: Tractable Reductions to Reachability (Invited Talk)
    Authors: Bouajjani, Ahmed ; Emmi, Michael ; Enea, Constantin ; Hamza, Jad

    Abstract | Document (268 KB) | BibTeX

    Reachability Problems for Continuous Linear Dynamical Systems (Invited Talk)
    Authors: Worrell, James

    Abstract | Document (274 KB) | BibTeX

    Convexity, Bayesianism, and the Quest Towards Optimal Algorithms (Invited Talk)
    Authors: Barak, Boaz

    Abstract | Document (216 KB) | BibTeX

    Beyond Matrix Completion (Invited Talk)
    Authors: Moitra, Ankur

    Abstract | Document (201 KB) | BibTeX

    Relational Refinement Types for Higher-Order Shape Transformers (Invited Talk)
    Authors: Jagannathan, Suresh

    Abstract | Document (218 KB) | BibTeX

    Robust Reoptimization of Steiner Trees
    Authors: Goyal, Keshav ; Mömke, Tobias

    Abstract | Document (583 KB) | BibTeX

    Minimizing Weighted lp-Norm of Flow-Time in the Rejection Model
    Authors: Roy Choudhury, Anamitra ; Das, Syamantak ; Kumar, Amit

    Abstract | Document (493 KB) | BibTeX

    On Correcting Inputs: Inverse Optimization for Online Structured Prediction
    Authors: Daumé III, Hal ; Khuller, Samir ; Purohit, Manish ; Sanders, Gregory

    Abstract | Document (505 KB) | BibTeX

    Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches
    Authors: Assadi, Sepehr ; Khanna, Sanjeev ; Li, Yang ; Tannen, Val

    Abstract | Document (516 KB) | BibTeX

    Weighted Strategy Logic with Boolean Goals Over One-Counter Games
    Authors: Bouyer, Patricia ; Gardy, Patrick ; Markey, Nicolas

    Abstract | Document (618 KB) | BibTeX

    Decidability in the Logic of Subsequences and Supersequences
    Authors: Karandikar, Prateek ; Schnoebelen, Philippe

    Abstract | Document (498 KB) | BibTeX

    Fragments of Fixpoint Logic on Data Words
    Authors: Colcombet, Thomas ; Manuel, Amaldev

    Abstract | Document (558 KB) | BibTeX

    Efficient Algorithms for Morphisms over Omega-Regular Languages
    Authors: Fleischer, Lukas ; Kufleitner, Manfred

    Abstract | Document (436 KB) | BibTeX

    Approximating the Regular Graphic TSP in Near Linear Time
    Authors: Chiplunkar, Ashish ; Vishwanathan, Sundar

    Abstract | Document (415 KB) | BibTeX

    On Weighted Bipartite Edge Coloring
    Authors: Khan, Arindam ; Singh, Mohit

    Abstract | Document (511 KB) | BibTeX

    Deciding Orthogonality in Construction-A Lattices
    Authors: Chandrasekaran, Karthekeyan ; Gandikota, Venkata ; Grigorescu, Elena

    Abstract | Document (448 KB) | BibTeX

    Ordered Tree-Pushdown Systems
    Authors: Clemente, Lorenzo ; Parys, Pawel ; Salvati, Sylvain ; Walukiewicz, Igor

    Abstract | Document (517 KB) | BibTeX

    One-way Definability of Sweeping Transducer
    Authors: Baschenis, Félix ; Gauwin, Olivier ; Muscholl, Anca ; Puppis, Gabriele

    Abstract | Document (596 KB) | BibTeX

    What's Decidable about Availability Languages?
    Authors: Abdulla, Parosh Aziz ; Atig, Mohamed Faouzi ; Meyer, Roland ; Seyed Salehi, Mehdi

    Abstract | Document (496 KB) | BibTeX

    Towards Better Separation between Deterministic and Randomized Query Complexity
    Authors: Mukhopadhyay, Sagnik ; Sanyal, Swagato

    Abstract | Document (460 KB) | BibTeX

    Dimension, Pseudorandomness and Extraction of Pseudorandomness
    Authors: Agrawal, Manindra ; Chakraborty, Diptarka ; Das, Debarati ; Nandakumar, Satyadev

    Abstract | Document (513 KB) | BibTeX

    On the NP-Completeness of the Minimum Circuit Size Problem
    Authors: Hitchcock, John M. ; Pavan, A.

    Abstract | Document (399 KB) | BibTeX

    Counting Euler Tours in Undirected Bounded Treewidth Graphs
    Authors: Balaji, Nikhil ; Datta, Samir ; Ganesan, Venkatesh

    Abstract | Document (567 KB) | BibTeX

    Revisiting Robustness in Priced Timed Games
    Authors: Guha, Shibashis ; Krishna, Shankara Narayanan ; Manasa, Lakshmi ; Trivedi, Ashutosh

    Abstract | Document (675 KB) | BibTeX

    Simple Priced Timed Games are not That Simple
    Authors: Brihaye, Thomas ; Geeraerts, Gilles ; Haddad, Axel ; Lefaucheux, Engel ; Monmege, Benjamin

    Abstract | Document (646 KB) | BibTeX

    Quantitative Games under Failures
    Authors: Brihaye, Thomas ; Geeraerts, Gilles ; Haddad, Axel ; Monmege, Benjamin ; Pérez, Guillermo A. ; Renault, Gabriel

    Abstract | Document (612 KB) | BibTeX

    Games with Delays - A Frankenstein Approach
    Authors: Berwanger, Dietmar ; van den Bogaard, Marie

    Abstract | Document (402 KB) | BibTeX

    Forbidden Extension Queries
    Authors: Biswas, Sudip ; Ganguly, Arnab ; Shah, Rahul ; Thankachan, Sharma V.

    Abstract | Document (690 KB) | BibTeX

    On Density, Threshold and Emptiness Queries for Intervals in the Streaming Model
    Authors: Bishnu, Arijit ; Chakrabarti, Amit ; Nandy, Subhas C. ; Sen, Sandeep

    Abstract | Document (574 KB) | BibTeX

    Clustering on Sliding Windows in Polylogarithmic Space
    Authors: Braverman, Vladimir ; Lang, Harry ; Levin, Keith ; Monemizadeh, Morteza

    Abstract | Document (564 KB) | BibTeX

    Congestion Games with Multisets of Resources and Applications in Synthesis
    Authors: Avni, Guy ; Kupferman, Orna ; Tamir, Tami

    Abstract | Document (679 KB) | BibTeX

    The Sensing Cost of Monitoring and Synthesis
    Authors: Almagor, Shaull ; Kuperberg, Denis ; Kupferman, Orna

    Abstract | Document (560 KB) | BibTeX

    An omega-Algebra for Real-Time Energy Problems
    Authors: Cachera, David ; Fahrenberg, Uli ; Legay, Axel

    Abstract | Document (609 KB) | BibTeX

    Parameterized Complexity of Secluded Connectivity Problems
    Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Karpov, Nikolay ; Kulikov, Alexander S.

    Abstract | Document (535 KB) | BibTeX

    Parameterized Algorithms for Deletion to (r,ell)-Graphs
    Authors: Kolay, Sudeshna ; Panolan, Fahad

    Abstract | Document (523 KB) | BibTeX

    Finding Even Subgraphs Even Faster
    Authors: Goyal, Prachi ; Misra, Pranabendu ; Panolan, Fahad ; Philip, Geevarghese ; Saurabh, Saket

    Abstract | Document (540 KB) | BibTeX

    The Parameterized Complexity of the Minimum Shared Edges Problem
    Authors: Fluschnik, Till ; Kratsch, Stefan ; Niedermeier, Rolf ; Sorge, Manuel

    Abstract | Document (510 KB) | BibTeX

    Control Improvisation
    Authors: Fremont, Daniel J. ; Donzé, Alexandre ; Seshia, Sanjit A. ; Wessel, David

    Abstract | Document (499 KB) | BibTeX

    A Provably Correct Sampler for Probabilistic Programs
    Authors: Hur, Chung-Kil ; Nori, Aditya V. ; Rajamani, Sriram K. ; Samuel, Selva

    Abstract | Document (1,069 KB) | BibTeX

    On the Problem of Computing the Probability of Regular Sets of Trees
    Authors: Michalewski, Henryk ; Mio, Matteo

    Abstract | Document (560 KB) | BibTeX

    Probabilistic Regular Expressions and MSO Logic on Finite Trees
    Authors: Weidner, Thomas

    Abstract | Document (549 KB) | BibTeX

    Rumors Across Radio, Wireless, Telephone
    Authors: Iglesias, Jennifer ; Rajaraman, Rajmohan ; Ravi, R. ; Sundaram, Ravi

    Abstract | Document (671 KB) | BibTeX

    The Price of Local Power Control in Wireless Scheduling
    Authors: Halldórsson, Magnús M. ; Tonoyan, Tigran

    Abstract | Document (544 KB) | BibTeX

    Allocation of Divisible Goods Under Lexicographic Preferences
    Authors: Schulman, Leonard J. ; Vazirani, Vijay V.

    Abstract | Document (1,021 KB) | BibTeX

    On the Expressiveness of Multiparty Sessions
    Authors: Demangeon, Romain ; Yoshida, Nobuko

    Abstract | Document (604 KB) | BibTeX

    Secure Refinements of Communication Channels
    Authors: Cheval, Vincent ; Cortier, Véronique ; le Morvan, Eric

    Abstract | Document (513 KB) | BibTeX

    Failure-aware Runtime Verification of Distributed Systems
    Authors: Basin, David ; Klaedtke, Felix ; Zalinescu, Eugen

    Abstract | Document (535 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI