|
|
Conference Programme
| Tuesday, 15 December, 2009 |
|
|
|
09:00-10:00
|
Invited Talk:
R. Ravi
Iterative Methods in Combinatorial Optimization
|
|
|
Chair:
Ravi Kannan
|
|
|
|
|
10:30-12:30
|
| 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
|
|
|
|
|
15:30-17:00
|
| 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
|
|
| |
|
| Wednesday, 16 December, 2009 |
|
09:00-10:00
|
Invited Talk:
Kim G. Larsen
Priced Timed Automata: Theory and Tools
|
|
|
Chair:
Madhavan Mukund
|
|
|
|
|
10:30-12:30
|
| 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
|
|
|
|
|
|
14:00-15:30
|
| 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
|
|
|
|
|
|
16:00-17:00
|
IARCS Business Meeting
|
|
19:30-22:00
|
Conference Banquet
|
|
| Thursday, 17 December, 2009 |
|
09:00-10:00
|
Invited Talk:
Avi Wigderson
Randomness extractors -- applications and constructions
|
|
|
Chair:
Satya Lokam
|
|
|
|
|
10:30-12:00
|
| 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
|
|
|
