FSTTCS 2012 Accepted Papers

FSTTCS 2012 Accepted Papers

  1. Rohit Khandekar, Kirsten Hildrum, Deepak Rajan and Joel Wolf. Scheduling with Setup Costs and Monotone Penalties
  2. Nathanael Fijalkow and Martin Zimmermann. Cost-Parity and Cost-Streett Games
  3. Andreas Krebs and Howard Straubing. An effective characterization of the alternation hierarchy in two-variable logic
  4. Salvatore La Torre and Gennaro Parlato. Scope-bounded Multistack Pushdown Systems: Fixed-Point, Sequentialization, and Tree-Width
  5. Krishnendu Chatterjee, Manas Joglekar and Nisarg Shah. Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Buchi Objectives
  6. Paul Bonsma. Rerouting shortest paths in planar graphs
  7. Hee-Kap Ahn, Siu-Wing Cheng, Hyuk Jun Kweon and Juyoung Yon. Overlap of Convex Polytopes under Rigid Motion
  8. Binay Bhattacharya and Yuzhuang Hu. k-Delivery traveling salesman problem on tree networks
  9. Minati De, Subhas Nandy and Sasanka Roy. Minimum Enclosing Circle with Few Extra Variables
  10. Swastik Kopparty and Srikanth Srinivasan. Certifying polynomials for AC^0(parity) circuits, with applications
  11. Kishore Kothapalli and Sriram Pemmaraju. Super-Fast 3-Ruling Sets
  12. Jakub Gajarsky and Petr Hlineny. Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences
  13. Gabor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha and Ronald de Wolf. New bounds on the classical and quantum communication complexity of some graph properties
  14. Guy Feigenblat, Ely Porat and Ariel Shiftan. Exponential Space Improvement for min-wise Based Algorithms
  15. Pranavadatta Devaki and Aditya Kanade. Static Analysis for Checking Data Format Compatibility of Programs
  16. Khaled Elbassio, Naveen Garg, Divya Gupta, Amit Kumar, Vishal Narula and Arindam Pal. Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees
  17. Amit Kumar, Preeti Panda and Smruti Sarangi. Efficient on-line algorithms for maintaining k-cover of sparse bit-strings
  18. Jonathan Hayman, Vincent Danos, Jérôme Feret, Walter Fontana, Russell Harmer, Jean Krivine, Chris Thompson-Walsh and Glynn Winskel. Graphs, Rewriting and Pathway Reconstruction for Rule-Based Models
  19. Rohit Chadha and Michael Ummels. The Complexity of Quantitative Information Flow in Recursive Programs
  20. Anthony Widjaja Lin. Accelerating tree-automatic relations
  21. Riccardo Traverso, Giorgio Delzanno, Arnaud Sangnier and Gianluigi Zavattaro. On the Complexity of Parameterized Reachability in Reconfigurable Broadcast Networks
  22. Navin Goyal and Luis Rademacher. Lower Bounds for the Average and Smoothed Number of Pareto Optima
  23. Udi Boker and Thomas Henzinger. Approximate Determinization of Quantitative Automata
  24. Laura Bozzelli and Cesar Sanchez. Visibly Rational Expressions
  25. Christopher Broadbent and Stefan Göller. On Bisimilarity of Higher-Order Pushdown Automata: Undecidability at Order Two
  26. Matthias Mnich, Geevarghese Philip, Saket Saurabh and Ondrej Suchy. Beyond Max-Cut: λ-Extendible Properties Parameterized Above the Poljak-Turzík Bound
  27. Tomas Brazdil, Holger Hermanns, Jan Krcal, Jan Kretinsky and Vojtech Rehak. Verification of Open Interactive Markov Chains
  28. Abhash Anand, Surender Baswana, Manoj Gupta and Sandeep Sen. Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs
  29. Vince Barany, Mikolaj Bojanczyk, Diego Figueira and Pawel Parys. Decidable classes of documents for XPath
  30. Johannes Köbler, Sebastian Kuhnert and Oleg Verbitsky. Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace
  31. Remi Bonnet, Alain Finkel and M. Praveen. Extending the Rackoff technique to Affine nets
  32. Varun Rajan. Space Efficient Edge Fault Tolerant Routing
  33. Jonathan Cederberg, Parosh Aziz Abdulla and Mohamed Faouzi Atig. Timed Lossy Channel Systems
  34. Andrea Turrini and Holger Hermanns. Deciding Probabilistic Automata Weak Bisimulation in Polynomial Time
  35. Kasturi Varadarajan and Xin Xiao. On the Sensitivity of Shape Fitting Problems
  36. Venkatesan Chakaravarthy, Natwar Modani, Sivaramakrishnan Natarajan, Sambuddha Roy and Yogish Sabharwal. Density Functions subject to a Co-Matroid Constraint
  37. Daniel Lokshtanov, Saket Saurabh and Magnus Wahlström. Subexponential Parameterized Odd Cycle Transversal on Planar Graphs
  38. Santosh Vempala. Randomly-Oriented k-d Trees Adapt to Intrinsic Dimension
  39. Vojtech Forejt, Petr Jancar, Stefan Kiefer and James Worrell. Bisimilarity of Probabilistic Pushdown Automata
  40. Gergei Bana, Pedro Adao and Hideki Sakurada. Computationally Complete Symbolic Attacker in Action
  41. Venkatesan Chakaravarthy, Arindam Pal, Sambuddha Roy and Yogish Sabharwal. Scheduling Resources for Executing a Partial Set of Jobs
  42. Alexander Heußner, Tristan Le Gall and Grégoire Sutre. Safety Verification of Communicating One-Counter Machines
  43. Robert Crowston, Gregory Gutin and Mark Jones. Directed Acyclic Subgraph Problem Parameterized above Raman-Saurabh Bound