FSTTCS 2012 December 15-17, 2012, Hyderabad, India

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)



Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan (Eds.)
ISBN 978-3-939897-47-7, LIPICS Vol. 18 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 22 MB)
Search Publication Server

Authors
  • Abdulla, Parosh Aziz
  • Achlioptas, Dimitris
  • Adao, Pedro
  • Ahn, Hee-Kap
  • Anand, Abhash
  • Atig, Mohamed Faouzi
  • Bana, Gergei
  • Bárány, Vince
  • Baswana, Surender
  • Bhattacharya, Binay
  • Bojanczyk, Mikolaj
  • Boker, Udi
  • Bonnet, Rémi
  • Bonsma, Paul
  • Bozzelli, Laura
  • Brazdil, Tomas
  • Broadbent, Christopher
  • Cederberg, Jonathan
  • Chadha, Rohit
  • Chakaravarthy, Venkatesan T.
  • Chatterjee, Krishnendu
  • Cheng, Siu-Wing
  • Crowston, Robert
  • Danos, Vincent
  • Delzanno, Giorgio
  • De, Minati
  • Devaki, Pranavadatta
  • de Wolf, Ronald
  • D'Souza, Deepak
  • Elbassioni, Khaled
  • Feigenblat, Guy
  • Feret, Jerome
  • Figueira, Diego
  • Fijalkow, Nathanael
  • Finkel, Alain
  • Fontana, Walter
  • Forejt, Vojtech
  • Gajarsky, Jakub
  • Garg, Naveen
  • Godefroid, Patrice
  • Göller, Stefan
  • Gouleakis, Themis
  • Goyal, Navin
  • Gupta, Divya
  • Gupta, Manoj
  • Gutin, Gregory
  • Harmer, Russell
  • Hayman, Jonathan
  • Henzinger, Thomas A.
  • Hermanns, Holger
  • Heußner, Alexander
  • Hildrum, Kirsten
  • Hlineny, Petr
  • Hu, Yuzhuang
  • Ivanyos, Gábor
  • Jancar, Petr
  • Joglekar, Manas
  • Jones, Mark
  • Kanade, Aditya
  • Khandekar, Rohit
  • Kiefer, Stefan
  • Klauck, Hartmut
  • Köbler, Johannes
  • Kopparty, Swastik
  • Kothapalli, Kishore
  • Krcal, Jan
  • Krebs, Andreas
  • Kretinsky, Jan
  • Krivine, Jean
  • Kuhnert, Sebastian
  • Kumar, Amit
  • Kweon, Hyuk Jun
  • La Torre, Salvatore
  • Lee, Troy
  • Le Gall, Tristan
  • Lin, Anthony Widjaja
  • Lokshtanov, Daniel
  • Mnich, Matthias
  • Modani, Natwar
  • Nandy, Subhas C.
  • Narula, Vishal
  • Natarajan, Sivaramakrishnan R.
  • Pal, Arindam
  • Pal, Arindam
  • Panda, Preeti R.
  • Parlato, Gennaro
  • Parthasarathy, Madhusudan
  • Parys, Pawel
  • Pemmaraju, Sriram
  • Philip, Geevarghese
  • Porat, Ely
  • Praveen, M.
  • Rabani, Yuval
  • Rademacher, Luis
  • Radhakrishnan, Jaikumar
  • Rajan, Deepak
  • Rajan, Varun
  • Rehak, Vojtech
  • Roy, Sambuddha
  • Roy, Sasanka
  • Sabharwal, Yogish
  • Sakurada, Hideki
  • Sánchez, César
  • Sangnier, Arnaud
  • Santha, Miklos
  • Sarangi, Smruti
  • Saurabh, Saket
  • Sen, Sandeep
  • Shah, Nisarg
  • Shiftan, Ariel
  • Srinivasan, Srikanth
  • Straubing, Howard
  • Suchy, Ondrej
  • Sutre, Grégoire
  • Telikepalli, Kavitha
  • Thompson-Walsh, Chris
  • Torunczyk, Szymon
  • Traverso, Riccardo
  • Turrini, Andrea
  • Ummels, Michael
  • Varadarajan, Kasturi
  • Vempala, Santosh S.
  • Verbitsky, Oleg
  • Wahlström, Magnus
  • Winskel, Glynn
  • Wolf, Joel
  • Worrell, James
  • Xiao, Xin
  • Yon, Juyoung
  • Zavattaro, Gianluigi
  • Zimmermann, Martin
    		•

    		  
    Frontmatter, Table of Contents, Preface, Conference Organization
    Authors: D'Souza, Deepak ; Radhakrishnan, Jaikumar ; Telikepalli, Kavitha

    Abstract | Document (316 KB) | BibTeX

    Learning Mixtures of Distributions over Large Discrete Domains
    Authors: Rabani, Yuval

    Abstract | Document (276 KB) | BibTeX

    Imperative Programming in Sets with Atoms
    Authors: Bojanczyk, Mikolaj ; Torunczyk, Szymon

    Abstract | Document (452 KB) | BibTeX

    Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion
    Authors: Achlioptas, Dimitris ; Gouleakis, Themis

    Abstract | Document (458 KB) | BibTeX

    Test Generation Using Symbolic Execution
    Authors: Godefroid, Patrice

    Abstract | Document (335 KB) | BibTeX

    Automated Reasoning and Natural Proofs for Programs Manipulating Data Structures
    Authors: Parthasarathy, Madhusudan

    Abstract | Document (235 KB) | BibTeX

    Certifying polynomials for AC^0(parity) circuits, with applications
    Authors: Kopparty, Swastik ; Srinivasan, Srikanth

    Abstract | Document (455 KB) | BibTeX

    Randomly-oriented k-d Trees Adapt to Intrinsic Dimension
    Authors: Vempala, Santosh S.

    Abstract | Document (425 KB) | BibTeX

    Lower Bounds for the Average and Smoothed Number of Pareto Optima
    Authors: Goyal, Navin ; Rademacher, Luis

    Abstract | Document (486 KB) | BibTeX

    Exponential Space Improvement for minwise Based Algorithms
    Authors: Feigenblat, Guy ; Porat, Ely ; Shiftan, Ariel

    Abstract | Document (533 KB) | BibTeX

    An effective characterization of the alternation hierarchy in two-variable logic
    Authors: Krebs, Andreas ; Straubing, Howard

    Abstract | Document (491 KB) | BibTeX

    Decidable classes of documents for XPath
    Authors: Bárány, Vince ; Bojanczyk, Mikolaj ; Figueira, Diego ; Parys, Pawel

    Abstract | Document (1,631 KB) | BibTeX

    Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences
    Authors: Gajarsky, Jakub ; Hlineny, Petr

    Abstract | Document (540 KB) | BibTeX

    Cost-Parity and Cost-Streett Games
    Authors: Fijalkow, Nathanael ; Zimmermann, Martin

    Abstract | Document (519 KB) | BibTeX

    Super-Fast 3-Ruling Sets
    Authors: Kothapalli, Kishore ; Pemmaraju, Sriram

    Abstract | Document (539 KB) | BibTeX

    New bounds on the classical and quantum communication complexity of some graph properties
    Authors: Ivanyos, Gábor ; Klauck, Hartmut ; Lee, Troy ; Santha, Miklos ; de Wolf, Ronald

    Abstract | Document (717 KB) | BibTeX

    On Bisimilarity of Higher-Order Pushdown Automata: Undecidability at Order Two
    Authors: Broadbent, Christopher ; Göller, Stefan

    Abstract | Document (531 KB) | BibTeX

    Scope-bounded Multistack Pushdown Systems: Fixed-Point, Sequentialization, and Tree-Width
    Authors: La Torre, Salvatore ; Parlato, Gennaro

    Abstract | Document (630 KB) | BibTeX

    Scheduling with Setup Costs and Monotone Penalties
    Authors: Khandekar, Rohit ; Hildrum, Kirsten ; Rajan, Deepak ; Wolf, Joel

    Abstract | Document (562 KB) | BibTeX

    Scheduling Resources for Executing a Partial Set of Jobs
    Authors: Chakaravarthy, Venkatesan T. ; Pal, Arindam ; Roy, Sambuddha ; Sabharwal, Yogish

    Abstract | Document (532 KB) | BibTeX

    Visibly Rational Expressions
    Authors: Bozzelli, Laura ; Sánchez, César

    Abstract | Document (621 KB) | BibTeX

    Safety Verification of Communicating One-Counter Machines
    Authors: Heußner, Alexander ; Le Gall, Tristan ; Sutre, Grégoire

    Abstract | Document (521 KB) | BibTeX

    Density Functions subject to a Co-Matroid Constraint
    Authors: Chakaravarthy, Venkatesan T. ; Modani, Natwar ; Natarajan, Sivaramakrishnan R. ; Roy, Sambuddha ; Sabharwal, Yogish

    Abstract | Document (463 KB) | BibTeX

    Efficient on-line algorithm for maintaining k-cover of sparse bit-strings
    Authors: Kumar, Amit ; Panda, Preeti R. ; Sarangi, Smruti

    Abstract | Document (337 KB) | BibTeX

    Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs
    Authors: Anand, Abhash ; Baswana, Surender ; Gupta, Manoj ; Sen, Sandeep

    Abstract | Document (501 KB) | BibTeX

    Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees
    Authors: Elbassioni, Khaled ; Garg, Naveen ; Gupta, Divya ; Kumar, Amit ; Narula, Vishal ; Pal, Arindam

    Abstract | Document (394 KB) | BibTeX

    Graphs, Rewriting and Pathway Reconstruction for Rule-Based Models
    Authors: Danos, Vincent ; Feret, Jerome ; Fontana, Walter ; Harmer, Russell ; Hayman, Jonathan ; Krivine, Jean ; Thompson-Walsh, Chris ; Winskel, Glynn

    Abstract | Document (978 KB) | BibTeX

    On the Complexity of Parameterized Reachability in Reconfigurable Broadcast Networks
    Authors: Delzanno, Giorgio ; Sangnier, Arnaud ; Traverso, Riccardo ; Zavattaro, Gianluigi

    Abstract | Document (228 KB) | BibTeX

    Extending the Rackoff technique to Affine nets
    Authors: Bonnet, Rémi ; Finkel, Alain ; Praveen, M.

    Abstract | Document (530 KB) | BibTeX

    Accelerating tree-automatic relations
    Authors: Lin, Anthony Widjaja

    Abstract | Document (527 KB) | BibTeX

    k-delivery traveling salesman problem on tree networks
    Authors: Bhattacharya, Binay ; Hu, Yuzhuang

    Abstract | Document (471 KB) | BibTeX

    Rerouting shortest paths in planar graphs
    Authors: Bonsma, Paul

    Abstract | Document (503 KB) | BibTeX

    Space Efficient Edge-Fault Tolerant Routing
    Authors: Rajan, Varun

    Abstract | Document (589 KB) | BibTeX

    Approximate Determinization of Quantitative Automata
    Authors: Boker, Udi ; Henzinger, Thomas A.

    Abstract | Document (546 KB) | BibTeX

    Timed Lossy Channel Systems
    Authors: Abdulla, Parosh Aziz ; Atig, Mohamed Faouzi ; Cederberg, Jonathan

    Abstract | Document (449 KB) | BibTeX

    Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace
    Authors: Köbler, Johannes ; Kuhnert, Sebastian ; Verbitsky, Oleg

    Abstract | Document (463 KB) | BibTeX

    Directed Acyclic Subgraph Problem Parameterized above the Poljak-Turzik Bound
    Authors: Crowston, Robert ; Gutin, Gregory ; Jones, Mark

    Abstract | Document (489 KB) | BibTeX

    Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound
    Authors: Mnich, Matthias ; Philip, Geevarghese ; Saurabh, Saket ; Suchy, Ondrej

    Abstract | Document (594 KB) | BibTeX

    Subexponential Parameterized Odd Cycle Transversal on Planar Graphs
    Authors: Lokshtanov, Daniel ; Saurabh, Saket ; Wahlström, Magnus

    Abstract | Document (532 KB) | BibTeX

    Deciding Probabilistic Automata Weak Bisimulation in Polynomial Time
    Authors: Hermanns, Holger ; Turrini, Andrea

    Abstract | Document (668 KB) | BibTeX

    Bisimilarity of Probabilistic Pushdown Automata
    Authors: Forejt, Vojtech ; Jancar, Petr ; Kiefer, Stefan ; Worrell, James

    Abstract | Document (565 KB) | BibTeX

    Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Büchi Objectives
    Authors: Chatterjee, Krishnendu ; Joglekar, Manas ; Shah, Nisarg

    Abstract | Document (507 KB) | BibTeX

    Verification of Open Interactive Markov Chains
    Authors: Brazdil, Tomas ; Hermanns, Holger ; Krcal, Jan ; Kretinsky, Jan ; Rehak, Vojtech

    Abstract | Document (553 KB) | BibTeX

    On the Sensitivity of Shape Fitting Problems
    Authors: Varadarajan, Kasturi ; Xiao, Xin

    Abstract | Document (517 KB) | BibTeX

    Overlap of Convex Polytopes under Rigid Motion
    Authors: Ahn, Hee-Kap ; Cheng, Siu-Wing ; Kweon, Hyuk Jun ; Yon, Juyoung

    Abstract | Document (573 KB) | BibTeX

    Minimum Enclosing Circle with Few Extra Variables
    Authors: De, Minati ; Nandy, Subhas C. ; Roy, Sasanka

    Abstract | Document (568 KB) | BibTeX

    Static Analysis for Checking Data Format Compatibility of Programs
    Authors: Devaki, Pranavadatta ; Kanade, Aditya

    Abstract | Document (494 KB) | BibTeX

    The Complexity of Quantitative Information Flow in Recursive Programs
    Authors: Chadha, Rohit ; Ummels, Michael

    Abstract | Document (495 KB) | BibTeX

    Computationally Complete Symbolic Attacker in Action
    Authors: Bana, Gergei ; Adao, Pedro ; Sakurada, Hideki

    Abstract | Document (546 KB) | BibTeX

    		  



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