Conference Programme

Tuesday, 9 December, 2008
08:00-09:00 Registration
09:00-10:00 Invited Talk: Leslie Valiant, Knowledge Infusion
Chair: Manindra Agrawal
10:00-10:30 Coffee break
Session 1A
Chair: Jaikumar Radhakrishnan
Chandra Chekuri and Nitish Korula
Single-Sink Network Design with Vertex Connectivity Requirements
Chandra Chekuri and Nitish Korula
Pruning 2-Connected Graphs and Applications
Sampath Kannan, Sanjeev Khanna and Sudeepa Roy
STCON on Directed Unique-Path Graphs
Alan Frieze and Ravindran Kannan
A new approach to the planted clique problem
Session 1B
Chair: S Arun-Kumar
Takahito Aoto
Sound Lemma Generation for Proving Inductive Validity of Equations
Georg Moser, Andreas Schnabl and Johannes Waldmann
Complexity Analysis of Term Rewriting Based on Matrix and Context Dependent Interpretations
Juan Rodriguez-Hortala
A Hierarchy of Semantics for Non-deterministic Term Rewriting Systems
Jonathan Hayman and Glynn Winskel
The unfolding of general Petri nets
12:30-14:00 Lunch
14:00-15:00 Invited Talk: Erich Grädel, Banach-Mazur Games on Graphs
Chair: K Narayan Kumar
15:00-15:30 Coffee break
Session 2A
Chair: V Arvind
Omid Amini, Fedor Fomin and Saket Saurabh
Implicit Branching and Parameterized Partial Cover Problems
André Chailloux and Iordanis Kerenidis
Increasing the power of the verifier in Quantum Zero Knowledge
Samir Datta, Nutan Limaye and Prajakta Nimbhorkar
3-connected Planar Graph Isomorphism is in Log-space
Session 2B
Chair: Kamal Lodaya
Didier Caucal
Boolean algebras of unambiguous context-free languages
Stefan Gulan and Henning Fernau
An Optimal Construction of Finite Automata from Regular Expressions
Kazuhiro Inaba and Sebastian Maneth
The Complexity of Tree Transducer Output Languages
17:00-18:00 IARCS Business Meeting

Wednesday, 10 December, 2008
09:00-10:00 Invited Talk: Simon Peyton Jones,
Harnessing the Multicores: Nested Data Parallelism in Haskell
Chair: Madhavan Mukund
10:00-10:30 Coffee break
Session 3A
Chair: Pranab Sen
Telikepalli Kavitha
Dynamic matrix rank with partial lookahead
Christian Komusiewicz and Johannes Uhlmann
A Cubic-Vertex Kernel for Flip Consensus Tree
Markus Lohrey
Leaf languages and string compression
Session 3B
Chair: Paul Gastin
Krishnendu Chatterjee, Luca de Alfaro, Rupak Majumdar and Vishwanath Raman
Algorithms for Game Metrics
Rayna Dimitrova and Bernd Finkbeiner
Abstraction Refinement for Games with Incomplete Information
Ashutosh Trivedi and Marcin Jurdzinski
Average-Time Games
12:00-14:00 Lunch
14:00-15:00 Invited Talk: Hubert Comon-Lundh, About Models of Security Protocols
Chair: Sanjiva Prasad
15:00-15:30 Coffee break
Session 4AB
Chair: Ravi Kannan
Noam Berger, Nevin Kapur, Leonard J Schulman and Vijay Vazirani
Solvency Games
Florian Horn
Explicit Muller Games are PTIME
18:30-22:00 Cultural Programme and Conference Banquet

Thursday, 11 December, 2008
09:00-10:00 Invited Talk: Uriel Feige,
On Estimation Algorithms versus Approximation Algorithms
Chair: Ramesh Hariharan
10:00-10:30 Coffee break
Session 5A
Chair: Telikepalli Kavitha
Vikraman Arvind and Pushkar Joglekar
Some Sieving Algorithms for Lattice Problems
Josep Diaz, Lefteris Kirousis, Dieter Mitsche and Xavier Perez-Gimenez
A new upper bound for 3-SAT
Daniel Golovin, Anupam Gupta, Amit Kumar and Kanat Tangwongsan
All-Norms and All-Lp-Norms Approximation Algorithms
Session 5B
Chair: Deepak D'Souza
Mohamed Faouzi Atig, Ahmed Bouajjani and Tayssir Touili
Analyzing Asynchronous Programs with Preemption
David Basin, Felix Klaedtke, Samuel Müller and Birgit Pfitzmann
Runtime Monitoring of Metric First-order Temporal Properties
Romain Péchoux and Jean-Yves Marion
Analyzing the Implicit Computational Complexity of object-oriented programs
12:00-14:00 Lunch
Session 6AB
Chair: Marcin Jurdzinski
Dietmar Berwanger and Laurent Doyen
On the power of imperfect information
Julien Cristau and Florian Horn
Graph Games on Ordinals