30. FSTTCS 2011: Chennai, India

• Supratik Chakraborty, Amit Kumar:
  Frontmatter, Table of Contents, Preface, Conference Organization, External Reviewers.
  
• Author Index.
  
• Susanne Albers:
  Energy-Efficient Algorithms (Invited Talk). 1-2
  
• Moshe Y. Vardi:
  Constraints, Graphs, Algebra, Logic, and Complexity (Invited Talk). 3-3
  
• Madhu Sudan:
  Physical limits of Communication (Invited Talk). 4-5
  
• Alex Bain, John C. Mitchell, Rahul Sharma, Deian Stefan, Joe Zimmerman:
  A Domain-Specific Language for Computing on Encrypted Data (Invited Talk). 6-24
  
• Phokion G. Kolaitis:
  Schema Mappings and Data Examples: Deriving Syntax from Semantics (Invited Talk). 25-25
  
• Umesh V. Vazirani:
  Quantum State Description Complexity (Invited Talk). 26-27
  
• Marek Cygan, Fabrizio Grandoni, Stefano Leonardi, Marcin Mucha, Marcin Pilipczuk, Piotr Sankowski:
  Approximation Algorithms for Union and Intersection Covering Problems. 28-40
  
• Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou, Avner Magen:
  Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy. 41-54
  
• Christian Glaßer, Christian Reitwießner, Maximilian Witek:
  Applications of Discrepancy Theory in Multiobjective Approximation. 55-65
  
• Denis Kuperberg, Michael Vanden Boom:
  Quasi-Weak Cost Automata: A New Variant of Weakness. 66-77
  
• Frédéric Herbreteau, Dileep Kini, B. Srivathsan, Igor Walukiewicz:
  Using non-convex approximations for efficient analysis of timed automata. 78-89
  
• Ocan Sankur, Patricia Bouyer, Nicolas Markey:
  Shrinking Timed Automata. 90-102
  
• Uli Fahrenberg, Axel Legay, Claus R. Thrane:
  The Quantitative Linear-Time--Branching-Time Spectrum. 103-114
  
• B. V. Raghavendra Rao, Jayalal M. N. Sarma:
  Isomorphism testing of read-once functions and polynomials. 115-126
  
• Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki:
  The Limited Power of Powering: Polynomial Identity Testing and a Depth-four Lower Bound for the Permanent. 127-139
  
• Philippe Darondeau, Stéphane Demri, Roland Meyer, Christophe Morvan:
  Petri Net Reachability Graphs: Decidability Status of FO Properties. 140-151
  
• Mohamed Faouzi Atig, Pierre Ganty:
  Approximating Petri Net Reachability Along Context-free Traces. 152-163
  
• Fedor V. Fomin, Geevarghese Philip, Yngve Villanger:
  Minimum Fill-in of Sparse Graphs: Kernelization and Approximation. 164-175
  
• Abhijin Adiga, L. Sunil Chandran, Rogers Mathew:
  Cubicity, Degeneracy, and Crossing Number. 176-190
  
• Harrie Jan Sander Bruggink, Raphaël Cauderlier, Mathias Hülsbusch, Barbara König:
  Conditional Reactive Systems. 191-203
  
• Céline Chevalier, Stéphanie Delaune, Steve Kremer:
  Transforming Password Protocols to Compose. 204-216
  
• Pinar Heggernes, Pim van 't Hof, Daniel Lokshtanov, Christophe Paul:
  Obtaining a Bipartite Graph by Contracting Few Edges. 217-228
  
• Robert Crowston, Michael R. Fellows, Gregory Gutin, Mark Jones, Frances A. Rosamond, Stéphan Thomassé, Anders Yeo:
  Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average. 229-240
  
• Prabhanjan Ananth, Meghana Nasre, Kanthi K. Sarpatwar:
  Rainbow Connectivity: Hardness and Tractability. 241-251
  
• Arnaud Durand, Johannes Ebbing, Juha Kontinen, Heribert Vollmer:
  Dependence logic with a majority quantifier. 252-263
  
• Emanuel Kieronski, Jakub Michaliszyn, Jan Otop:
  Modal Logics Definable by Universal Three-Variable Formulas. 264-275
  
• Stefan Göller, Markus Lohrey:
  The First-Order Theory of Ground Tree Rewrite Graphs. 276-287
  
• Bertram Felgenhauer, Harald Zankl, Aart Middeldorp:
  Layer Systems for Proving Confluence. 288-299
  
• Aleksander Madry, Debmalya Panigrahi:
  The Semi-stochastic Ski-rental Problem. 300-311
  
• Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, Frédéric Servais:
  Streamability of Nested Word Transductions. 312-324
  
• Manoj Gupta, Yogish Sabharwal, Sandeep Sen:
  The update complexity of selection and related problems. 325-338
  
• Yang Cai, Ting Zhang:
  A Tight Lower Bound for Streett Complementation. 339-350
  
• Pablo Barceló, Leonid Libkin, Juan L. Reutter:
  Parameterized Regular Expressions and Their Languages. 351-362
  
• Jacques Duparc, Alessandro Facchini, Filip Murlak:
  Definable Operations On Weakly Recognizable Sets of Trees. 363-374
  
• Patricia Bouyer, Romain Brenguier, Nicolas Markey, Michael Ummels:
  Nash Equilibria in Concurrent Games with Büchi Objectives. 375-386
  
• Dietmar Berwanger, Lukasz Kaiser, Bernd Puchala:
  A Perfect-Information Construction for Coordination in Games. 387-398
  
• John Fearnley, Markus Rabe, Sven Schewe, Lijun Zhang:
  Efficient Approximation of Optimal Control for Continuous-Time Markov Games. 399-410
  
• Nathalie Bertrand, Blaise Genest:
  Minimal Disclosure in Partially Observable Markov Decision Processes. 411-422
  
• Oren Ben-Kiki, Philip Bille, Dany Breslauer, Leszek Gasieniec, Roberto Grossi, Oren Weimann:
  Optimal Packed String Matching. 423-432
  
• Saverio Caminiti, Irene Finocchi, Emanuele G. Fusco, Francesco Silvestri:
  Dynamic programming in faulty memory hierarchies (cache-obliviously). 433-444
  
• Hongfei Fu, Joost-Pieter Katoen:
  Deciding Probabilistic Simulation between Probabilistic Pushdown Automata and Finite-State Systems. 445-456
  
• Matthew Hague:
  Parameterised Pushdown Systems with Non-Atomic Writes. 457-468
  
• Didier Caucal, Teodor Knapik:
  Higher order indexed monadic systems. 469-480
  

Last update Wed May 23 00:47:23 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page