|
Conference Programme
Tuesday, 9 December, 2008 |
|
09:00-10:00
|
Invited Talk:
Leslie Valiant,
Knowledge Infusion
|
|
Chair:
Manindra Agrawal
|
|
|
10:30-12:30
|
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
|
|
|
|
14:00-15:00
|
Invited Talk:
Erich Grädel,
Banach-Mazur Games on Graphs
|
|
Chair:
K Narayan Kumar
|
|
|
15:30-17:00
|
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:30-12:00
|
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
|
|
|
|
14:00-15:00
|
Invited Talk:
Hubert Comon-Lundh,
About Models of Security Protocols
|
|
Chair:
Sanjiva Prasad
|
|
|
15:30-16:30
|
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:30-12:00
|
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
|
|
|
|
14:00-15:00
|
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
|
|
|
|