Venue:

Venue for talks, lunches, tea/coffee breaks, etc. are indicated in [...] in the schedule below. LCH 31 and 32 refer to auditoria on the third floor of the Lecture Hall Complex opposite KReSIT Building (see map). LCH 31/32 foyer refers to the foyer between auditoria LCH 31 and 32 on the third floor. Lunch will be served in the banquet hall on the third floor of Gulmohur building, which is five minutes' walking distance from the Lecture Hall Complex.

FSTTCS 2011 Program

Monday, December 12, 2011
8:00 - 8:45	Registration [LCH 31/32 foyer]
8:45 - 9:00	Inauguration and welcome address [LCH 31]
9:00 - 10:00	Invited Talk [LCH 31] Susanne Albers, Energy-Efficient Algorithms Chair: Amit Kumar
10:00 - 10:30	Tea/Coffee Break [LCH 31/32 foyer]
10:30 - 12:30	Session 1A : Approximation Algorithms [LCH 31] Chair: Abhiram Ranade	Session 1B: Automata/Logics with Time and Cost [LCH 32] Chair: Paritosh K. Pandya
	Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk and Piotr Sankowski, Approximation Algorithms for Union and Intersection Covering Problems	Denis Kuperberg and Michael Vanden Boom, Quasi-Weak Cost Automata: A New Variant of Weakness
	Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou and Avner Magen, Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy	Frédéric Herbreteau, Dileep Kini, B Srivathsan and Igor Walukiewicz, Using non-convex approximations for efficient analysis of timed automata
	Christian Glasser, Christian Reitwießner and Maximilian Witek, Applications of Discrepancy Theory in Multiobjective Approximation	Ocan Sankur, Patricia Bouyer and Nicolas Markey, Shrinking Timed Automata
		Uli Fahrenberg, Axel Legay and Claus Thrane, The Quantitative Linear-Time Branching-Time Spectrum
12:30 - 14:00	Lunch Break [Gulmohur Building 3rd floor]
Monday, December 12, 2011
14:00 - 15:00	Invited Talk [LCH 31] Moshe Y. Vardi, Constraints, Graphs, Algebra, Logic and Complexity Chair: R. Ramanujam
15:00 - 16:00	Session 2A: Complexity Theory [LCH 31] Chair: Ragesh Jaiswal	Session 2B: Petri Nets [LCH 32] Chair: Kamal Lodaya
	Raghavendra Rao B V and Jayalal M.N. Sarma, Isomorphism testing of read-once functions and polynomials	Philippe Darondeau, Stéphane Demri, Roland Meyer and Christophe Morvan, Petri Net Reachability Graphs: Decidability Status of FO Properties
	Bruno Grenet, Pascal Koiran, Natacha Portier and Yann Strozecki, The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent	Mohamed Faouzi Atig and Pierre Ganty, Approximating Petri Net Reachability Along Context-free Traces
16:00 - 16:30	Tea/Coffee Break [LCH 31/32 foyer]
16:30 - 17:30	Session 3A: Graph-theoretic Algorithms [LCH 31] Chair: T. Kavitha	Session 3B: Reactive and Password Systems [LCH 32] Chair: G. Sivakumar
	Fedor V. Fomin, Geevarghese Philip and Yngve Villanger, Minimum Fill-in of Sparse Graphs: Kernelization and Approximation	Sander Bruggink, Raphaël Cauderlier, Mathias Hülsbusch and Barbara König, Conditional Reactive Systems
	Abhijin Adiga, L. Sunil Chandran and Rogers Mathew, Cubicity, Degeneracy, and Crossing Number	Céline Chevalier, Stephanie Delaune and Steve Kremer,Transforming Password Protocols to Compose
18:30 - 20:30	Cultural Event by Pta. Shubhada Paradkar [VMCC auditorium]

Tuesday, December 13, 2011
9:00 - 10:00	Invited Talk [LCH 31] Madhu Sudan, Physical Limits of Communication Chair: Neeraj Kayal
10:00 - 10:30	Tea/Coffee Break [LCH 31/32 foyer]
10:30 - 12:30	Session 4A: Parameterized Complexity [LCH 31] Chair: Nutan Limaye	Session 4B: Logics and Proofs [LCH 32] Chair: Dietmar Berwanger
	Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov and Christophe Paul, Obtaining a bipartite graph by contracting few edges	[Rescheduled to session 7B due to presenter's unavailability] Johannes Ebbing, Arnaud Durand, Juha Kontinen and Heribert Vollmer, Dependence logic with a majority quantifier
	Robert Crowston, Michael Fellows, Gregory Gutin, Mark Jones, Frances Rosamond, Stéphan Thomassé and Anders Yeo, Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average	Jakub Michaliszyn, Emanuel Kieroński and Jan Otop, Modal Logics Definable by Universal Three-Variable Formulas
	Prabhanjan Ananth, Meghana Nasre and Kanthi Sarpatwar, Rainbow Connectivity: Hardness and Tractability	Stefan Göller and Markus Lohrey, The First-Order Theory of Ground Tree Rewrite Graphs
		Bertram Felgenhauer, Harald Zankl and Aart Middeldorp, Layer Systems for Proving Confluence
12:30 - 14:00	Lunch Break [Gulmohur Building 3rd floor]
14:00 - 15:00	Invited Talk [LCH 31] John Mitchell, A Domain-Specific Lamguage for Computing on Encrypted Data Chair: Madhavan Mukund
15:00 - 16:30	Session 5A: Online and Streaming Algorithms [LCH 31] Chair: Naveen Garg	Session 5B: Automata Theory and Regular Languages [LCH 32] Chair: K. Narayan Kumar
	Aleksander Madry and Debmalya Panigrahi, The Semi-Stochastic Ski Rental Problem	Yang Cai and Ting Zhang, A Tight Lower Bound for Streett Complementation
	Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier and Frédéric Servais, Streamability of Nested Word Transductions	Pablo Barceló, Leonid Libkin and Juan L. Reutter, Parameterized Regular Expressions and Their Languages
	Manoj Gupta, Yogish Sabharwal and Sandeep Sen, The Update Complexity of Selection and Related Problems	Jacques Duparc, Alessandro Facchini and Filip Murlak, Definable Operations On Weakly Recognizable Sets of Trees
16:30 - 17:00	Tea/Coffee Break [LCH 31/32 foyer]
17:00 - 18:00	IARCS Business Meeting [LCH 31]
19:00 - 22:00	Conference Banquet [Hotel Meluha The Fern, Hiranandani, Powai]

Wednesday, December 14, 2011
9:00 - 10:00	Invited Talk [LCH 31] Phokion G. Kolaitis, Schema Mappings and Data Examples: An Interplay Between Syntax and Semantics Chair: S. Sudarshan
10:00 - 10:30	Tea/Coffee Break [LCH 31/32 foyer]
10:30 - 12:30	Session 6: Games [LCH 32] Chair: Krishnendu Chatterjee
	Patricia Bouyer, Romain Brenguier, Nicolas Markey and Michael Ummels, Nash Equilibria in Concurrent Games with Büchi Objectives
	Dietmar Berwanger, Kaiser Lukasz and Bernd Puchala, Perfect-Information Construction for Coordination in Games
	John Fearnley, Markus Rabe, Sven Schewe and Lijun Zhang, Efficient Approximation of Optimal Control for Continuous-Time Markov Games
	Nathalie Bertrand and Blaise Genest, Minimal Disclosure in Partially Observable Markov Decision Processes
12:30 - 14:00	Lunch Break [Gulmohur Building 3rd floor]
14:00 - 15:00	Invited Talk [LCH 31] Umesh Vazirani, Quantum State Description Complexity Chair: Jaikumar Radhakrishnan
15:00 - 16:50	Session 7A: Memory Efficient Algorithms [LCH 31] Chair: Sandeep Sen	Session 7B: Pushdown Systems [LCH 32] Chair: Anil Seth
	Oren Ben-Kiki, Philip Bille, Dany Breslauer, Roberto Grossi and Oren Weimann, Optimal Packed String Matching	Hongfei Fu and Joost-Pieter Katoen, Deciding Probabilistic Simulation between Probabilistic Pushdown Automata and Finite-State Systems
	Saverio Caminiti, Irene Finocchi, Emanuele Guido Fusco and Francesco Silvestri, Dynamic programming in faulty memory hierarchies (cache-obliviously)	Matthew Hague, Parameterised Pushdown Systems with Non-Atomic Writes
		Didier Caucal and Teodor Knapik, Higher order indexed monadic systems
		[Missed talk from Session 4B] Johannes Ebbing, Arnaud Durand, Juha Kontinen and Heribert Vollmer, Dependence logic with a majority quantifier
16:50 - 17:00	Closing Remarks [LCH 32]
17:00 - 17:15	Tea/Coffee Break [LCH 31/32 foyer]
END OF CONFERENCE