FSTTCS 2006

The 26th Conference on Foundations of Software Technology and Theoretical Computer Science

December 13-15, 2006
Indian Statistical Institute
Kolkata, INDIA

Preliminary Programme (13, 14 and 15 December 2006)
(A 2-day schedule has also been put up in case 14 Dec has to be washed off due to a strike by Trade Unions.) Click here for the 2-day programme

13 Dec 2006
8:30-9:30 Registration
Invited Talk
9:30-10:30
Hennessy-Plotkin-Brookes Revisited
G. D. Plotkin

Chair: S. Arun-Kumar
10:30-11:00 Tea/Coffee
Session A1.1 Chair: Naveen Garg B1.1 Chair: Kamal Lodaya
11:00-11:30 Self-assembling classes of shapes, fast and with a minimal number of tiles
F Becker, I Rapaport and E Rémila
The Meaning of Ordered SOS
M.R. Mousavi, I.C.C. Phillips, M.A. Reniers and I. Ulidowski
11:30-12:00 Hardness of Approximation results for the problem of finding the Stopping Distance in Tanner Graphs
K. Murali Krishnan, L. Sunil Chandran
The anatomy of innocence revisited
R. Harmer and O. Laurent
12:00-12:30 Fast edge colorings with fixed number of colors to minimize imbalance
G. Calinescu and M.J. Pelsmajer
Context-Sensitive Dependency Pairs
B. Alarcón, R. Gutiérrez, and S. Lucas
12:30-13:30 Lunch
Invited Talk
13:30-14:30
The Number of Crossing Free Configurations on Finite Point Sets
Emo Welzl

Chair: Naveen Garg
14:30-15:00 Tea/Coffee
Session A1.2 Chair: Manindra Agrawal B1.2 Chair: Paritosh Pandya
15:00-15:30 One-input-face MPCVP is Hard for L, but in LogDCFL
T. Chakraborty and S. Datta
On Decidability of LTL Model Checking for Process Rewrite Systems
L. Bozzelli, M. Kretinsky, V. Rehak and J. Strejcek
15:30-16:00 Computationally Sound Symbolic Secrecy in the Presence of Hash Functions
V Cortier, S. Kremer, R. Kusters and B. Warinschi
Safely Freezing LTL
R. Lazić
16:00-16:30 Some Results on Average-case Hardness Within the Polynomial Hierarchy
A. Pavan, R. Santhanam and V. Vinodchandran
Distributed synthesis for well-connected architectures
P. Gastin, N. Sznajder and M. Zeitoun




Business Meeting




Conference Banquet




14 Dec 2006
8:30-9:30 Registration
Invited Talk
9:30-10:30
Shared-Variable Concurrency: A Proposal
G. Boudol

Chair: Madhavan Mukund
10:30-11:00 Tea/Coffee
Session A2.1 Chair: Yuval Rabani B2.1 Chair: Astrid Kiehn
11:00-11:30 Multi-Stack Boundary Labeling Problems
M. A. Bekos, M. Kaufmann, K. Potika and A. Symvonis
Game semantics For Higher-Order Concurrency
Jim Laird
11:30-12:00 Linear-time Algorithms for Two Subtree-Comparison Problems on Phylogenetic Trees with Different Species
Sun-Yuan Hsieh
Rational Behaviour and Strategy Construction in Infinite Multiplayer Games
M. Ummels
12:00-12:30 Unbiased Rounding of Rational Matrices
B. Doerr, C. Klein
Testing Probabilistic Equivalence through Reinforcement Learning
J. Desharnais, F. Laviolette and S. Zhioua
12:30-13:30 Lunch
Invited Talk
13:30-14:30
Approximate Algorithms for 2-stage Stochastic Optimization
David B. Shmoys

Chair: Amit Kumar
14:30-15:00 Tea/Coffee
Session A2.2 Chair: Rana Barua B2.2 Chair: Sanjiva Prasad
15:00-15:30 On obtaining pseudorandomness from error-correcting codes
S Kalyanaraman and C Umans
Branching pushdown tree automata
R. Alur, S. Chaudhuri
15:30-16:00 Zero-error list decoding capacity of the q/(q-1) channel
Sourav Chakraborty, Jaikumar Radhakrishnan, Nandakumar Raghunathan and Prashant Sasatte
Tree automata make ordinal theory easy
T Cachat
16:00-16:30
Expressivity properties of Boolean BI through relational models
D. Galmiche and D. Larchey-Wendling




15 Dec 2006
8:30-9:30 Registration
Invited Talk
9:30-10:30
All That Noise!
Eugene Asarin

Chair: Deepak D'Souza
10:30-11:00 Tea/Coffee
Session A3.1 Chair: Sudeb Pal B3.1 Chair: Supratik Chakraborty
11:00-11:30 Normal and Feature Approximations from Noisy Point Clouds
Tamal K. Dey and Jian Sun
On continuous timed automata with input-determined guards
F. Chevalier, D. D'Souza and P. Prabhakar
11:30-12:00 Coresets for Discrete Integration and Clustering
S. Har-Peled
Almost Optimal Strategies in One Clock Priced Timed Automata
P. Bouyer, K. G. Larsen, N. Markey, J. I. Rasmussen
12:00-12:30 Computing a Center-Transversal Line
P. K. Agarwal, S. Cabello, J. A. Sellarès and M. Sharir
Monitoring of Realtime Properties
A. Bauer, M. Leucker, C. Schallhart
12:30-13:30 Lunch
Sponsor's Talk
14:00-14:30


IBM-IRL
14:30-15:00 Tea/Coffee
Session A3.2 Chair: Bhabhani P Sinha B3.2 Chair: Narayan Kumar
15:00-15:30 Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems
S. Gupta, V. Raman and S. Saurabh
On reduction criteria for probabilistic reward models
M. Groesser, G. Norman, C. Baier, F. Ciesinski, M. Kwiatkowska and D. Parker
15:30-16:00 Solving Connected Dominating Set Faster than 2^n
F. V. Fomin, F. Grandoni and D. Kratsch
Validity Checking for Finite Automata over Linear Arithmetic Constraints
G. Wassermann, Z. Su
16:00-16:30
A Proof System for the Linear Time μ-Calculus
C Dax and M Hofmann and M Lange









Alternative Programme (13 and 15 December 2006)

13 Dec 2006
8:00-9:00 Registration
Invited Talk
9:00-10:00
Hennessy-Plotkin-Brookes Revisited
G. D. Plotkin

Chair: S. Arun-Kumar
10:00-10:15  
Session A1.1 Chair: Naveen Garg B1.1 Chair: Kamal Lodaya
10:15-10:40 Self-assembling classes of shapes, fast and with a minimal number of tiles
F Becker, I Rapaport and E Rémila
The Meaning of Ordered SOS
M.R. Mousavi, I.C.C. Phillips, M.A. Reniers and I. Ulidowski
10:40-11:05 Hardness of Approximation results for the problem of finding the Stopping Distance in Tanner Graphs
K. Murali Krishnan, L. Sunil Chandran
The anatomy of innocence revisited
R. Harmer and O. Laurent
10:05-11:30 Fast edge colorings with fixed number of colors to minimize imbalance
G. Calinescu and M.J. Pelsmajer
Context-Sensitive Dependency Pairs
B. Alarcón, R. Gutiérrez, and S. Lucas
11:30-12:00 Tea/Coffee
Invited Talk
12:00-13:00
The Number of Crossing Free Configurations on Finite Point Sets
Emo Welzl

Chair: Naveen Garg
13:00-14:00 Lunch
Session A1.2 Chair: Manindra Agrawal B1.2 Chair: Paritosh Pandya
14:00-14:25 One-input-face MPCVP is Hard for L, but in LogDCFL
T. Chakraborty and S. Datta
On Decidability of LTL Model Checking for Process Rewrite Systems
L. Bozzelli, M. Kretinsky, V. Rehak and J. Strejcek
14:25-14:50 Computationally Sound Symbolic Secrecy in the Presence of Hash Functions
V Cortier, S. Kremer, R. Kusters and B. Warinschi
Safely Freezing LTL
R. Lazić
14:50-15:15 Some Results on Average-case Hardness Within the Polynomial Hierarchy
A. Pavan, R. Santhanam and V. Vinodchandran
Distributed synthesis for well-connected architectures
P. Gastin, N. Sznajder and M. Zeitoun
15:15-15:45 Tea/Coffee
Invited Talk
15:45-16:45
Shared-Variable Concurrency: A Proposal
G. Boudol

Chair: Madhavan Mukund
16:45-17:00  
Session A2.1 Chair: Yuval Rabani B2.1 Chair: Astrid Kiehn
17:00-17:25 Multi-Stack Boundary Labeling Problems
M. A. Bekos, M. Kaufmann, K. Potika and A. Symvonis
Game semantics For Higher-Order Concurrency
Jim Laird
17:25-17:50 Linear-time Algorithms for Two Subtree-Comparison Problems on Phylogenetic Trees with Different Species
Sun-Yuan Hsieh
Rational Behaviour and Strategy Construction in Infinite Multiplayer Games
M. Ummels
17:50-18:15 Unbiased Rounding of Rational Matrices
B. Doerr, C. Klein
Testing Probabilistic Equivalence through Reinforcement Learning
J. Desharnais, F. Laviolette and S. Zhioua




Business Meeting




Conference Banquet




15 Dec 2006
8:00-9:00 Registration
Invited Talk
9:00-10:00
All That Noise!
Eugene Asarin

Chair: Deepak D'Souza
10:00-10:15  
Session A3.1 Chair: Sudeb Pal B3.1 Chair: Supratik Chakraborty
10:15-10:40 Normal and Feature Approximations from Noisy Point Clouds
Tamal K. Dey and Jian Sun
On continuous timed automata with input-determined guards
F. Chevalier, D. D'Souza and P. Prabhakar
10:40-11:05 Coresets for Discrete Integration and Clustering
S. Har-Peled
Almost Optimal Strategies in One Clock Priced Timed Automata
P. Bouyer, K. G. Larsen, N. Markey, J. I. Rasmussen
10:05-11:30 Computing a Center-Transversal Line
P. K. Agarwal, S. Cabello, J. A. Sellarès and M. Sharir
Monitoring of Realtime Properties
A. Bauer, M. Leucker, C. Schallhart
11:30-12:00 Tea/Coffee
Invited Talk
12:00-13:00
Approximate Algorithms for 2-stage Stochastic Optimization
David B. Shmoys

Chair: Amit Kumar
13:00-14:00 Lunch
14:00-14:30 Sponsor's Talk: IBM-IRL
14:30-14:45  
Session A3.2 Chair: Bhabhani P Sinha B3.2 Chair: Narayan Kumar
14:45-15:10 Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems
S. Gupta, V. Raman and S. Saurabh
On reduction criteria for probabilistic reward models
M. Groesser, G. Norman, C. Baier, F. Ciesinski, M. Kwiatkowska and D. Parker
15:10-15:35 Solving Connected Dominating Set Faster than 2^n
F. V. Fomin, F. Grandoni and D. Kratsch
Validity Checking for Finite Automata over Linear Arithmetic Constraints
G. Wassermann, Z. Su
15:35-16:00
A Proof System for the Linear Time μ-Calculus
C Dax and M Hofmann and M Lange
16:00-16:30 Tea/Coffee
Session A2.2 Chair: Rana Barua B2.2 Chair: Sanjiva Prasad
16:30-16:55 On obtaining pseudorandomness from error-correcting codes
S Kalyanaraman and C Umans
Branching pushdown tree automata
R. Alur, S. Chaudhuri
16:55-17:20 Zero-error list decoding capacity of the q/(q-1) channel
Sourav Chakraborty, Jaikumar Radhakrishnan, Nandakumar Raghunathan and Prashant Sasatte
Tree automata make ordinal theory easy
T Cachat
17:20-17:45
Expressivity properties of Boolean BI through relational models
D. Galmiche and D. Larchey-Wendling


Last modified: Sat Dec 9 11:01:05 2006