30. FSTTCS 2011:
Chennai,
India
Supratik Chakraborty, Amit Kumar (Eds.):
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011, December 12-14, 2011, Mumbai, India.
LIPIcs 13 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik 2011, ISBN 978-3-939897-34-7
- 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