FSTTCS 2012 Program

Saturday, December 15, 2012

8:00 - 8:45

Registration [SH-1]

8:45 - 9:00

Inauguration and welcome address [SH-1]

9:00 - 10:00

Invited Talk [SH-1]

Yuval Rabani, Learning Mixtures of Distributions over Large Discrete Domains

Chair: Jaikumar Radhakrishnan

10:00 - 10:30

Tea/Coffee Break [Inbetween SH-1 and B6-309]

10:30 - 12:30

Session 1A: Complexity [SH-1]

Chair: Jaikumar Radhakrishnan

Session 1B: Logic and Games [B6-309]

Chair: Madhavan Mukund


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

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

Santosh Vempala, Randomly-Oriented k-d Trees Adapt to Intrinsic Dimension

Vince Barany, Mikołaj Bojańczyk, Diego Figueira and Pawel Parys, Decidable classes of documents for XPath

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

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

Venkatesan Chakaravarthy, Natwar Modani, Sivaramakrishnan Natarajan, Sambuddha Roy and Yogish Sabharwal, Density Functions subject to a Co-Matroid Constraint

Nathanael Fijalkow and Martin Zimmermann, Cost-Parity and Cost-Streett Games

12:30 - 14:00

Lunch Break [Guest House]

14:00 - 15:00

Invited Talk [SH-1]

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

Chair: K. Narayan Kumar

15:00 - 15:10

Short Break

15:10 - 16:10

Session 2A: Distributed Models [SH-1]

Chair: Sourav Chakraborty

Session 2B: Pushdown Automata [B6-309]

Chair: Anil Seth


Kishore Kothapalli and Sriram Pemmaraju, Super-Fast 3-Ruling Sets

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

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

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

16:10 - 16:40

Tea/Coffee Break [Inbetween SH-1 and B6-309]

16:40 - 17:40

Session 3A: Scheduling [SH-1]

Chair: Sourav Chakraborty

Session 3B: Automata [B6-309]

Chair: Supratik Chakraborty


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

Laura Bozzelli and Cesar Sanchez, Visibly Rational Expressions

Venkatesan Chakaravarthy, Arindam Pal, Sambuddha Roy and Yogish Sabharwal, Scheduling Resources for Executing a Partial Set of Jobs

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

17:45 - 18:30

Business Meeting [B6-309]


Sunday, December 16, 2012

9:00 - 10:00

Invited Talk [SH-1]

Mikołaj Bojańczyk, Imperative Programming in Sets with Atoms

Chair: Kamal Lodaya

10:00 - 10:30

Tea/Coffee Break [Inbetween SH-1 and B6-309]

10:30 - 12:30

Session 4A: Approximation Algorithms [SH-1]

Chair: Kavitha Telikepalli

Session 4B: Rewriting and Reachability [B6-309]

Chair: Sanjiva Prasad


Guy Feigenblat, Ely Porat and Ariel Shiftan, Exponential Space Improvement for minwise Based Algorithms

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

Amit Kumar, Preeti Panda and Smruti Sarangi, Efficient on-line algorithms for maintaining k-cover of sparse bit-strings

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

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

Remi Bonnet, Alain Finkel and M. Praveen, Extending the Rackoff technique to Affine nets

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

Anthony Widjaja Lin, Accelerating tree-automatic relations

12:30 - 14:00

Lunch Break [Guest House]

14:00 - 15:00

Invited Talk [SH-1]

Dimitris Achlioptas, Randomness in Networks: can less be more?

Chair: Amit Deshpande

15:00 - 15:10

Short Break

15:10 - 16:40

Session 5A: Path Computation [SH-1]

Chair: Amit Deshpande

Session 5B: Timed and Quantitative Systems [B6-309]

Chair: Aditya Kanade


Binay Bhattacharya and Yuzhuang Hu, k-Delivery traveling salesman problem on tree networks

Udi Boker and Thomas Henzinger, Approximate Determinization of Quantitative Automata

Paul Bonsma, Rerouting shortest paths in planar graphs

Jonathan Cederberg, Parosh Aziz Abdulla and Mohamed Faouzi Atig, Timed Lossy Channel Systems

Varun Rajan, Space Efficient Edge Fault Tolerant Routing

16:30 - 17:00

Tea/Coffee Break [Inbetween SH-1 and B6-309]

18:00 - 19:30

Cultural Event

19:30 - 22:00

Conference Banquet [Venue]


Monday, December 17, 2012

9:00 - 10:00

Invited Talk [SH-1]

Patrice Godefroid, Test Generation Using Symbolic Execution

Chair: Deepak D'Souza

10:00 - 10:30

Tea/Coffee Break [Inbetween SH-1 and B6-309]

10:30 - 12:30

Session 6A: Graph Algorithms [SH-1]

Chair: Kishore Kothapalli

Session 6B: Probabalistic Automata [B6-309]

Chair: Parosh Aziz Abdulla


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

Andrea Turrini and Holger Hermanns, Deciding Probabilistic Automata Weak Bisimulation in Polynomial Time

Robert Crowston, Gregory Gutin and Mark Jones, Directed Acyclic Subgraph Problem Parameterized above Raman-Saurabh Bound

Vojtech Forejt, Petr Jancar, Stefan Kiefer and James Worrell, Bisimilarity of Probabilistic Pushdown Automata

Matthias Mnich, Geevarghese Philip, Saket Saurabh and Ondrej Suchy, Beyond Max-Cut: Lambda-Extendible Properties Parameterized Above the Poljak-Turzík Bound

Krishnendu Chatterjee, Manas Joglekar and Nisarg Shah, Average Case Analysis of the Classical Algorithm for Markov Decision Processes with Buchi Objectives

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

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

12:30 - 14:00

Lunch Break [Guest House]

14:00 - 15:30

Session 7A: Geometry [SH-1]

Chair: Rahul Jain

Session 7B: Program Analysis and Security [B6-309]

Chair: Nishant Sinha


Kasturi Varadarajan and Xin Xiao, On the Sensitivity of Shape Fitting Problems

Pranavadatta Devaki and Aditya Kanade, Static Analysis for Checking Data Format Compatibility of Programs

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

Rohit Chadha and Michael Ummels, The Complexity of Quantitative Information Flow in Recursive Programs

Minati De, Subhas Nandy and Sasanka Roy, Minimum Enclosing Circle with Few Extra Variables

Gergei Bana, Pedro Adao and Hideki Sakurada, Computationally Complete Symbolic Attacker in Action

15:30 - 15:40

Closing Remarks [SH-1]

15:40 - 16:10

Tea/Coffee Break [Inbetween SH-1 and B6-309]

END OF CONFERENCE