FSTTCS 2010: Programme

Wednesday, 15 December, 2010
12:40-14:00 Lunch
13:30-14:30 Registration
14:30-15:30 Invited Talk: Wiesław Zielonka
Playing in stochastic environment: from multi-armed bandits to two-player games
Chair: Kamal Lodaya
15:30-16:00 Coffee break
16:00-17:30
Session 1A
Chair: Fedor Fomin
Petr Hlineny, Robert Ganian and Jan Obdrzalek.
Better algorithms for satisfiability problems for formulas of bounded rank-width
Sebastian Ordyniak, Daniel Paulusma and Stefan Szeider.
Satisfiability of Acyclic and Almost Acyclic CNF Formulas
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman and Saket Saurabh.
The effect of girth on the kernelization complexity of Connected Dominating Set
Session 1B
Chair: R Ramanujam
Tomas Brazdil, Vaclav Brozek and Kousha Etessami.
One-Counter Stochastic Games
Arnaud Da Costa, Francois Laroussinie and Nicolas Markey.
Expressiveness and decidability of ATL with strategy contexts
Fabio Mogavero, Aniello Murano and Moshe Vardi.
Reasoning About Strategies

Thursday, 16 December, 2010
09:00-10:00 Invited Talk: Rajeev Alur
Streaming String Transducers
Chair: Paritosh Pandya
10:00-10:30 Coffee break
10:30-11:30
11.40-12.40
Session 2A
Chair: Jaikumar Radhakrishnan
Sourav Chakraborty, Eldar Fischer, Arie Matsliah and Ronald de Wolf.
New Results on Quantum Property Testing
André Chailloux, Iordanis Kerenidis and Jamie Sikora.
Lower bounds for Quantum Oblivious Transfer
Rohit Khandekar, Baruch Schieber, Hadas Shachnai and Tami Tamir.
Approximating the Busy Times of Multiple Machines under Real-time Scheduling
Venkatesan Chakaravarthy, Anamitra Choudhury and Yogish Sabharwal.
A Near-linear Time Constant Factor Algorithm for UFP on Line with Bags
Session 2B
Chair: Supratik Chakraborty
Remi Bonnet, Alain Finkel, Jérome Leroux and Marc Zeitoun.
Place-Boundedness for Vector Addition Systems with one zero-test
S. Akshay, Paul Gastin, Madhavan Mukund and K. Narayan Kumar.
Model checking  time-constrained scenario-based specifications
Mohamed Faouzi Atig.
Global  Model Checking of Ordered Multi-Pushdown Systems
Matthew Hague and Anthony Widjaja To.
The Complexity of Model Checking (Collapsible) Higher-Order Pushdown Systems
12:40-14:00 Lunch
14:00-15:00 Invited Talk: Santosh Vempala
Recent Progress and Open Problems in Algorithmic Convex Geometry
Chair: Martin Fürer
15:00-15:30 Coffee break
15:30-17:00
Session 3A
Chair: Martin Fürer
Qi Ge and Daniel Stefankovic.
A graph polynomial for independent sets of bipartite graphs
Venkatesan Chakaravarthy, Vinayaka Pandit, Sambuddha Roy and Yogish Sabharwal.
Finding Independent Sets in Unions of Perfect Graphs
Session 3B
Chair: Sanjiva Prasad
Wojciech Czerwiński and Sławomir Lasota.
Fast equivalence-checking for normed context-free processes
Alexandra Silva, Filippo Bonchi, Marcello Bonsangue and Jan Rutten.
Generalizing the powerset construction, coalgebraically
Nicholas Radcliffe and Rakesh Verma.
Uniqueness of Normal Forms is Decidable for Shallow Term Rewrite Systems
17:15-18:00 IARCS Business Meeting
19:00 Conference Banquet

Friday, 17 December, 2010
09:00-10:00 Invited Talk: Pavel Pudlák
On extracting computations from propositional proofs
Chair: V. Arvind
10:00-10:30 Coffee break
10:30-11:30
11:40-12:40
Session 4A
Chair: Somenath Biswas
Maurice Jansen, Youming Qiao and Jayalal M.N. Sarma.
Deterministic Black-Box Identity Testing $\pi$-Ordered Algebraic Branching Programs
Paul Hunter, Patricia Bouyer, Nicolas Markey, Joël Ouaknine and James Worrell.
Computing rational radical sums in uniform TC^0
Arkadev Chattopadhyay, Jacobo Torán and Fabian Wagner.
Graph Isomorphism is not AC^0 reducible to Group Isomorphism
Vikraman Arvind, Bireswar Das, Johannes Koebler and Seinosuke Toda.
Colored Hypergraph Isomorphism is Fixed Parameter Tractable
Session 4B
Chair: Deepak D'Souza
Sara Capecchi, Elena Giachino and Nobuko Yoshida.
Global Escape in Multiparty Sessions
Michael Backes, Matteo Maffei and Esfandiar Mohammadi.
Computationally Sound Abstraction and Verification of Secure Multi-Party Computations
Rohit Chadha, A. Prasad Sistla and Mahesh Viswanathan.
Model Checking Concurrent Programs with Nondeterminism and Randomization
Eugene Asarin and Aldric Degorre.
Two Size Measures for Timed Languages
12:40-14:00 Lunch
14:00-15:30
Session 5
Chair: K Narayan Kumar
Cyril Nicaud, Carine Pivoteau and Benoît Razet.
Average Analysis of Glushkov Automata under a BST-Like Model
Sven Schewe.
Beyond Hyper-Minimisation--Minimising DBAs and DPAs is NP-Complete
Udi Boker, Orna Kupferman and Avital Steinitz.
Parityizing Rabin and Streett
15:30-16:00 Coffee break
16:00-17:30 Panel Discussion Session:
Under-graduate and graduate curricula in theoretical computer science
Coordinator: R Ramanujam
Panelists: Somenath Biswas, Michael Fellows, Madhavan Mukund

Saturday, 18 December, 2010
09:00-10:00 Invited Talk: Bruno Courcelle
Special tree-width and the verification of monadic second-order graph properties
Chair: Anil Seth
10:00-10:30 Coffee break
10:30-11:30
11:40-12:40
Session 6A
Chair: Meena Mahajan
Piotr Berman, Sofya Raskhodnikova and Ge Ruan.
Finding Sparser Directed Spanners
Pushkar Tripathi, Gagan Goel and Lei Wang.
Combinatorial Problems with Discounted Price Functions in Multi-agent Systems
Rishi Saket.
Quasi-Random PCP and Hardness of 2-Catalog Segmentation
Michael Fellows, Bart Jansen, Daniel Lokshtanov, Frances A. Rosamond and Saket Saurabh.
Determining the Winner of a Dodgson Election is Hard
Session 6B
Chair: Madhavan Mukund
Blaise Genest, Anca Muscholl and Zhilin Wu.
Verifying Recursive Active Documents with Positive Data Tree Rewriting
Ahmet Kara, Thomas Schwentick and Thomas Zeume.
Temporal Logics on Words with Multiple Data Values
Stefan Schulz.
First-Order Logic with Reachability Predicates on Infinite Systems
Jean-Francois Raskin, Krishnendu Chatterjee, Laurent Doyen and Thomas Henzinger.
Generalized Mean-payoff and Energy Games
12:40-14:00 Lunch