Conference Videos FSTTCS

FSTTCS 2009 Local Arrangements has recorded the proceedings of FSTTCS 2009. The talk videos are given as links below.
Only talks presented in the seminar room CS101 have been recorded.
There were problems with the recording of the following talk whose link is missing - we regret this technical failure.
Wednesday, 16 December, Session 3A : Kernels for Feedback Arc Set In Tournaments (Speaker: Anthony Perez)

Tuesday, 15 December, 2009
09:00-10:00 Invited Talk: R. Ravi
Iterative Methods in Combinatorial Optimization
Chair: Ravi Kannan
Session 1A
Chair: Piyush Kurur
Vikraman Arvind, Pushkar Joglekar and Srikanth Srinivasan.
Arithmetic Circuits and the Hadamard Product of Polynomials
Mark Braverman, Stephen Cook, Pierre McKenzie, Rahul Santhanam and Dustin Wehr.
Fractional Pebbling and Thrifty Branching Programs
Abhinav Kumar, Satyanarayana Lokam, Vijay M. Patankar and Jayalal M.N. Sarma.
Using Elimination Theory to construct Rigid Matrices
Chandan Saha, Ramprasad Saptharishi and Nitin Saxena.
The Power of Depth 2 Circuits over Algebras
Session 1B
Chair: R Ramanujam
Parosh Abdulla, Yu-Fang Chen, Lukas Holik and Tomas Vojnar.
Mediating for Reduction (on Minimizing Alternating Buchi Automata)
Mikołaj Bojańczyk and Szymon Toruńczyk.
Deterministic Automata and Extensions of Weak MSO
Jeremie Cabessa, Jacques Duparc, Alessandro Facchini and Filip Murlak.
The Wadge Hierarchy of Max-Regular Languages
Stephanie Delaune, Steve Kremer and Olivier Pereira.
Simulation based security in the applied pi calculus
14:00-15:00 Invited Talk: Anuj Dawar
Structure and Specification as Sources of Complexity
Chair: Anil Seth
Session 2A
Chair: Jaikumar Radhakrishnan
Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf and Fabian Wagner.
Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space
John Hitchcock, A Pavan and N. V Vinodchandran.
Kolmogorov Complexity in Randomness Extraction
Marc Kaplan, Iordanis Kerenidis, Sophie Laplante and Jérémie Rolan
Non-Local Box Complexity and Secure Function Evaluation
Session 2B
Chair: Kamal Lodaya
Tomas Brazdil, Javier Esparza and Stefan Kiefer.
On the Memory Consumption of Probabilistic Pushdown Automata
Mark Kattenbelt and Michael Huth.
Verification and refutation of probabilistic specifications via games
Mathieu Tracol, Marcus Groesser and Christel Baier.
Recurrence and Transience for Probabilistic Automata
17:15-18:00 Remembering Rajeev Motwani
Part I
Part II
Chair: Somenath Biswas

Wednesday, 16 December, 2009
09:00-10:00 Invited Talk: Kim G. Larsen
Priced Timed Automata: Theory and Tools
Part I
Part II
Chair: Madhavan Mukund
Session 3A
Chair: Navin Goyal
Stéphane Bessy, Fedor Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh and Stéphan Thomassé
Kernels for Feedback Arc Set In Tournaments
Fedor Fomin, Daniel Lokshtanov, Venkatesh Raman and Saket Saurabh.
Subexponential Algorithms for Partial Cover Problems
Anuj Dawar and Stephan Kreutzer.
Domination Problems in Nowhere-Dense Classes of Graphs
Joachim Kneis, Alexander Langer and Peter Rossmanith
A Fine-grained Analysis of a Simple Independent Set Algorithm
Session 3B
Chair: Dietmar Berwanger
Laurent Braud.
Covering of ordinals
Julien Cristau.
Automata and temporal logic over arbitrary linear time
Alexander Rabinovich.
Synthesis of Finite-state and DefinableWinning Strategies
Soumya Paul and Sunil Easaw Simon
Nash Equilibrium in Generalised Muller Games
Session 4A
Chair: Venkatesh Raman
Konstantinos Georgiou, Avner Magen and Iannis Tourlakis.
On the Tightening of the Standard SDP for Vertex Cover with $\ell_1$ Inequalities
Chien-Chung Huang and Zoya Svitkina.
Donation Center Location Problem
Rohit Khandekar, Guy Kortsarz and Zeev Nutov.
Approximating Fault-Tolerant Group-Steiner Problems
Session 4B
Chair: Sanjiva Prasad
Tomas Brazdil, Vojtech Forejt, Jan Krcal, Jan Kretinsky and Antonin Kucera.
Continuous-Time Stochastic Games with Time-Bounded Reachability
Laura Bozzelli, Axel Legay and Sophie Pinchinat.
On Timed Alternating Simulation for Concurrent Timed Games
Ankur Taly and Ashish Tiwari.
Deductive Verification of Continuous Dynamical Systems

Thursday, 17 December, 2009
09:00-10:00 Invited Talk: Avi Wigderson
Randomness extractors -- applications and constructions
Chair: Satya Lokam
Session 5A
Chair: Amit Kumar
Mostafa Ammar, Deeparnab Chakrabarty, Atish Das Sarma, Subrahmanyam Kalyanasundaram and Richard J. Lipton.
Algorithms for Message Ferrying on Mobile ad hoc Networks
Rohit Khandekar, Kirsten Hildrum, Sujay Parekh, Deepak Rajan, Jay Sethuraman and Joel Wolf.
Bounded Size Graph Clustering with Applications to Stream Processing
Andre Madeira and S. Muthukrishnan.
Functionally Private Approximations of Negligibly-Biased Estimators
Session 5B
Chair: Deepak D'Souza
Christof Loeding and Karianto Wong.
On Nondeterministic Unranked Tree Automata with Sibling Constraints
Stephane Demri, Marcin Jurdzinski, Oded Lachish and Ranko Lazic.
The covering and boundedness problems for branching vector addition systems
M. Praveen and Kamal Lodaya.
Modelchecking counting properties of 1-safe nets with buffers in paraPSPACE
12:15-12:30 Closing Session